第一次用dijkstra,只有参考网上代码修改了
http://my.oschina.net/u/235391/blog/96218
#include <iostream> #include <map> #include <cstring> using namespace std; #define INF 9999999 int dist[210][210]; int len[210]; bool judge[210]; int dijkstra(int a, int b, int k) { memset(judge,0,sizeof(judge)); for(int i = 0; i < k; i++) len[i] = INF; len[a] = 0; for(int i = 0; i < k; i++) { int min = INF; int t = a; for(int j = 0; j < k; j++) if(!judge[j] && len[j]<min) { min = len[j]; t = j; } judge[t] = true; for(int j = 0; j < k; j++) if(!judge[j] && len[t]+dist[t][j] < len[j]) len[j] = len[t]+dist[t][j]; } if(judge[b]) return len[b]; else return -1; } int main(int argc, char const *argv[]) { int t,n,l; string a, b; cin >> t; while(t--) { cin >> n; map<string,int>m; int cnt = 0; for(int i = 0; i < 210; i++) for(int j = 0; j < 210; j++) dist[i][j] = (i == j?0:INF); for(int i = 0; i < n; i++) { cin >> a >> b >> l; if(!m.count(a)) m[a] = cnt++; if(!m.count(b)) m[b] = cnt++; dist[m[a]][m[b]] = dist[m[b]][m[a]] = l; } cin >> a >> b; if(a==b) cout << 0 << endl; else if(!m.count(a) || !m.count(b)) cout << -1 << endl; else cout << dijkstra(m[a],m[b],cnt) << endl; } return 0; }