此题主要是要用到字符串向整数的映射 ， 很自然的想到了 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 ;}elsemymap[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 ;
}
