? ? ? ?一道最短路問題。普通最短路問題的邊只有一種權值，而此題的邊要考慮兩種權值。因為節點n<=1000，所以不能夠使用Floyd算法，時間復雜度較高，這里使用Dijkstra算法解決。
? ? ? ?中文描述，題意不再贅述。只是要注意每條邊都有距離和花費兩種權，當且僅當兩條邊的距離相等時才比較花費。因為需要考慮兩種權，所以算法代碼要有相應的改變。另外，要考慮重邊的問題，依舊要考慮兩種權值。
? ? ? ?下面是解題代碼：Dijkstra解法
?
1 #include <stdio.h> 2 #define N 1001 3 #define INF 9999999 4 5 int map[N][N]; /*距離圖*/ 6 int cost[N][N]; /*花費圖*/ 7 int dis[N]; /*起點到i的距離*/ 8 int cos[N]; /*起點到i的花費*/ 9 int flag[N]; /*標志變量*/ 10 int n, m; 11 int s, t; 12 13 void Init(); /*初始化*/ 14 15 void Read(); /*輸入*/ 16 17 void Dijkstra(); 18 19 int main() 20 { 21 while (~scanf("%d %d", &n, &m)) 22 { 23 if (n == 0 && m == 0) 24 { 25 break; 26 } 27 Init(); 28 Read(); 29 Dijkstra(); 30 printf("%d %d\n", dis[t], cos[t]); 31 } 32 return 0; 33 } 34 35 void Init() /*初始化*/ 36 { 37 int i, j; 38 for (i=1; i<=n; ++i) 39 { 40 for (j=1; j<=n; ++j) 41 { 42 map[i][j] = cost[i][j] = INF; 43 } 44 dis[i] = cos[i] = INF; 45 flag[i] = 0; 46 } 47 return; 48 } 49 50 void Read() /*輸入*/ 51 { 52 int i; 53 int a, b, c, d; 54 for (i=0; i<m; ++i) 55 { 56 scanf("%d %d %d %d", &a, &b, &c, &d); 57 if (map[a][b] > c || (map[a][b] == c && cost[a][b] > d)) /*解決重邊*/ 58 { 59 map[a][b] = map[b][a] = c; 60 cost[a][b] = cost[b][a] = d; 61 } 62 } 63 scanf("%d %d", &s, &t); 64 return; 65 } 66 67 void Dijkstra() 68 { 69 int i, j, k; 70 int mind, minc; 71 dis[s] = cos[s] = 0; 72 for (i=1; i<=n; ++i) 73 { 74 mind = minc = INF; 75 for (j=1; j<=n; ++j) 76 { 77 /*多權值的比較*/ 78 if (flag[j] == 0 && (mind > dis[j] || (mind == dis[j] && minc > cos[j]))) 79 { 80 mind = dis[k = j]; 81 minc = cos[k]; 82 } 83 } 84 flag[k] = 1; 85 for (j=1; j<=n; ++j) 86 { 87 if (flag[j] == 0 && dis[j] > dis[k] + map[k][j]) 88 { 89 dis[j] = dis[k] + map[k][j]; 90 cos[j] = cos[k] + cost[k][j]; 91 } 92 /*當距離相同時考慮花費*/ 93 if (flag[j] == 0 && dis[j] == dis[k] + map[k][j] && cos[j] > cos[k] + cost[k][j]) 94 { 95 cos[j] = cos[k] + cost[k][j]; 96 } 97 } 98 } 99 return; 100 }
)
