SPFA, Dijkstra, Floyd 都可以.
注意两点之间有重边, 所以要选择最小的.
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
/**//*
ID: lorelei3
TASK: comehome
LANG: C++
*/
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
#include <fstream>
#include <queue>
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
using namespace std;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
const int MAX = 256;
const int INF = 999999999;
int map[MAX][MAX];
int dist[MAX];
bool isInQ[MAX],f[MAX];
int N;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
inline bool relax(int u, int v)
{
int len = dist[u]+map[u][v];
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if(len<dist[v])
{
dist[v] = len;
return true;
}
return false;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
void spfa()
{
queue<int> Q;
int be = 'Z',t=0;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
dist[be]=0;
map[be][be]=0;
Q.push(be);
isInQ[be]=true;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
while(!Q.empty())
{
int u = Q.front();
Q.pop();
isInQ[u]=false;
for(int v=0; v<MAX; ++v)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if(relax(u, v) && !isInQ[v])
{
Q.push(v);
isInQ[v]=true;
}
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
int main()
{
int i,j,v,ans=INF, loc=0;
char ch1,ch2;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
ifstream fin("comehome.in");
ofstream fout("comehome.out");
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for(i=0; i<MAX; ++i)
{
for(j=0; j<MAX; ++j)
map[i][j]=INF;
dist[i] = INF;
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
fin>>N;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for(i=0; i<N; ++i)
{
fin>>ch1>>ch2>>v;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if(v<map[ch1][ch2])
{
map[ch1][ch2]=v;
map[ch2][ch1]=v;
}
if(ch1>='A' && ch1<'Z')
f[ch1]=true;
if(ch2>='A' && ch2<'Z')
f[ch2]=true;
}
spfa();
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
for(i=0; i<MAX; ++i)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if(dist[i]<ans && f[i] )
{
ans = dist[i];
loc= i;
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
fout<<(char)loc<<' '<<ans<<endl;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
return 0;
}
posted on 2010-12-10 21:23
小阮 阅读(317)
评论(0) 编辑 收藏 引用 所属分类:
USACO