此题主要是要用到字符串向整数的映射 ， 很自然的想到了 STL 中的map ，哎，贡献无数次WA，最后才发现每次运行时 map 忘了清空 ！！！！本题，用dijkstra 和 spfa 均可 ，但是要记着提交时用C++ ，用G++的话可能会超时。 此题为无向图，还应注意当出发站和终点站相同时输出 0 ！！我用dijkstra 和 spfa 均能过，请看代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<queue>
#include<cmath>
#include<map>
using namespace std ;
const int MAXN = 1005 ;
const int INF = 0x7fffffff ;
struct Node
{
int adj ;
int dist ;
Node * next ;
};
int cnt ;
Node *vert[MAXN] ; // 建立顶点头指针数组
int vis[MAXN] ;
int dis[MAXN] ; // 建立距离数组
map<string , int> mymap ;
void dijkstra(int v0)
{
int i ;
for ( i = 1 ; i <= cnt ; i ++)
{
dis[i] = INF ;
}
dis[v0] = 0 ;
vis[v0] = 1 ;
int min = INF ;
int u = v0 ;
Node * p ;
for (i = 1 ; i <= cnt - 1 ; i ++)
{
p = vert[u] ;
while (p != NULL)
{
int ty = p -> adj ;
int td = p -> dist ;
if(!vis[ty] && dis[u] + td <= dis[ty])
{
dis[ty] = dis[u] + td ;
}
p = p -> next ;
}
int j ;
min = INF ;
for(j = 1 ; j <= cnt ; j ++)
{
if(!vis[j] && dis[j] < min)
{
u = j ;
min = dis[j] ;
}
}
vis[u] = 1 ;
}
}
queue <int> mq ;
int inq[MAXN] ;
void spfa(int v0)
{
memset(inq , 0 , sizeof(inq)) ;
while (!mq.empty()) // 队列清空
mq.pop() ;
mq.push(v0) ;
inq[v0] ++ ;
int tmp ;
Node * p ;
int i ;
for( i = 1 ; i <= cnt ; i ++)
{
dis[i] =INF ;
}
dis[v0] = 0 ;
while (!mq.empty())
{
tmp = mq.front() ;
mq.pop() ;
inq[tmp] -- ;
p = vert[tmp] ;
while (p != NULL)
{
int tadj = p -> adj ;
int td = p -> dist ;
int tk ;
tk = dis[tmp] + td ;
if(dis[tmp] < INF && tk < dis[tadj] )
{
dis[tadj] = tk ;
if(inq[tadj] == 0)
{
mq.push(tadj) ;
inq[tadj] ++ ;
}
}
p = p -> next ;
}
} }
int main()
{
int n ;
while (scanf("%d", & n) != EOF)
{
if(n == -1)
break ;
memset(vis , 0 , sizeof(vis)) ;
memset(vert , 0 , sizeof(vert)) ;
mymap.clear() ; // 千万不要忘了把 map 清空 ！！
cnt = 0 ;
string s1 , s2 ;
cin >> s1 ;
mymap[s1] = ++ cnt ;
cin >> s2 ;
int pan = 0 ;
if(s1 == s2)
{
pan = 1 ;
}
else
mymap[s2] = ++ cnt ;
int i ;
for (i = 0 ; i < n ; i ++)
{
string st1 ;
string st2 ;
int d ;
cin >> st1 >> st2 >> d ;
if(mymap.find(st1) == mymap.end())
{
mymap[st1] = ++ cnt ;
}
if(mymap.find(st2) == mymap.end())
{
mymap[st2] = ++ cnt ;
}
int t1 , t2 ;
t1 = mymap[st1] ;
t2 = mymap[st2] ;
Node * p ;
p = new Node ; // 建立邻接表
p -> adj = t2 ;
p -> dist = d ;
p -> next = vert[t1] ;
vert[t1] = p ; p = new Node ;
p -> adj = t1 ;
p -> dist = d ;
p -> next = vert[t2] ;
vert[t2] = p ;
}
if(pan == 1)
{
printf("0\n") ;
continue ;
}
//dijkstra(1) ;
spfa(1) ;
if(dis[2] < INF)
{
printf("%d\n" , dis[2]) ;
}
else
{
printf("-1\n") ;
}
}
return 0 ;
}