//hdu2112 用map映射结点的编号
//链接http://acm.hdu.edu.cn/showproblem.php?pid=2112
1 #include<cstdio> 2 #include<iostream> 3 #include<string> 4 #include<cstring> 5 #include<map> 6 using namespace std; 7 8 const int INF = 0x3f3f3f3f; 9 const int MAXN = 150 + 15; 10 11 string s, e; 12 map<string, int> discnt; 13 14 int cnt; 15 int G[MAXN][MAXN]; 16 17 int dis[MAXN]; 18 int vis[MAXN]; 19 void dijkstra() { 20 if(s == e) { 21 printf("0\n"); 22 return ; 23 } 24 for(int i = 0; i != cnt; ++i) { 25 dis[i] = G[discnt[s]][i]; 26 vis[i] = 0; 27 } 28 vis[discnt[s]] = 1; 29 for(int i = 0; i != cnt-1; ++i) { 30 int minn = INF; 31 int t = -1; 32 for(int j = 0; j != cnt; ++j) { 33 if(!vis[j] && dis[j] < minn) { 34 minn = dis[j]; 35 t = j; 36 } 37 } 38 if(t == -1) break; 39 vis[t] = 1; 40 for(int j = 0; j != cnt; ++j) { 41 if(dis[j] > dis[t]+G[t][j]) { 42 dis[j] = dis[t] + G[t][j]; 43 } 44 } 45 } 46 if(dis[discnt[e]] != INF) printf("%d\n", dis[discnt[e]]); 47 else printf("-1\n"); 48 } 49 50 int main() { 51 int n; 52 while(scanf("%d", &n) == 1 && n != -1) { 53 memset(G, INF, sizeof(G)); 54 cin >> s >> e; 55 string a, b; 56 discnt.clear(); 57 cnt = 0; 58 discnt[a] = ++cnt; 59 discnt[b] = ++cnt; 60 int c; 61 for(int i = 0; i != n; ++i) { 62 cin >> a >> b >> c; 63 if(!discnt.count(a)) discnt[a] = cnt++; 64 if(!discnt.count(b)) discnt[b] = cnt++; 65 if(c < G[discnt[a]][discnt[b]]) { 66 G[discnt[a]][discnt[b]] = G[discnt[b]][discnt[a]] = c; 67 } 68 } 69 dijkstra(); 70 } 71 return 0; 72 }
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 using namespace std; 5 6 #define INF 0x3f3f3f3f 7 #define MAX 502 8 int N, M, S, D; 9 int mp[MAX][MAX], cost[MAX][MAX]; 10 int path[MAX], vis[MAX]; 11 int dis[MAX], mincost[MAX]; 12 13 void Dijkstar(){ 14 for(int i = 0; i != N; ++i){ 15 dis[i] = mp[S][i]; 16 mincost[i] = cost[S][i]; 17 path[i] = S;//记录的是上一个节点 18 } 19 vis[S] = 1; 20 for(int i = 0; i < N-1; ++i){ 21 int m = INF, m_c = INF; 22 int t; 23 for(int j = 0; j != N; ++j){ 24 if(!vis[j] && m > dis[j]){ 25 m = dis[j]; 26 m_c = mincost[j]; 27 t = j; 28 } 29 } 30 vis[t] = 1; 31 for(int j = 0; j != N; ++j){ 32 if(!vis[j]){ 33 if(dis[j] > mp[t][j] + m){ 34 dis[j] = mp[t][j] + m; 35 mincost[j] = cost[t][j] + m_c; 36 path[j] = t; 37 } 38 else if(dis[j] == mp[t][j] + m && mincost[j] > cost[t][j] + m_c){ 39 dis[j] = mp[t][j] + m; 40 mincost[j] = cost[t][j] + m_c; 41 path[j] = t; 42 } 43 } 44 } 45 } 46 int index = D, top = 0; 47 int stack[MAX]; 48 while(index != S){ 49 stack[top++] = index; 50 index = path[index]; 51 } 52 cout << S << " "; 53 top--; 54 while(top >=0){ 55 cout << stack[top--] << " "; 56 } 57 cout << dis[D] << " " << mincost[D] << endl; 58 } 59 60 int main() 61 { 62 cin >> N >> M >> S >> D; 63 memset(mp, 0x3f, sizeof(mp)); 64 memset(cost, 0x3f, sizeof(cost)); 65 memset(vis, 0, sizeof(vis)); 66 int a, b, s, c; 67 for(int i = 0; i != M; ++i){ 68 scanf("%d%d%d%d", &a, &b, &s, &c); 69 if(s < mp[a][b] || (s == mp[a][b] && c < cost[a][b])){ 70 mp[a][b] = mp[b][a] = s; 71 cost[a][b] = cost[b][a] = c; 72 } 73 } 74 Dijkstar(); 75 return 0; 76 }
原文：https://www.cnblogs.com/pupil-xj/p/11564176.html