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