題意概括：有N個城市和M條道路，任意兩個城市之間都有可能超過一種以上的可能。求任意兩個城市之間的最短距離。

解題思路：1：典型的多源最短路徑問題。

代碼思路：

１：用一個二維數組ｅ來存儲任意兩個城市之間的距離，用ｉｎｆ　＝　９９９９９９９９來初始化存儲除一個城市自己到自己之外的所有距離，用ｉｎｔ　ｎ，　ｍ分別作為城市數和道路數。

int e[202][202]; int inf = 99999999, n, m;

２：先輸入ｎ，　ｍ，分別為城市數和道路數，然后用一個二重ｆｏｒ循環來初始化城市之間的距離，如果是一個城市自己到自己，則置為０；否則置為ｉｎｆ。

scanf("%d%d", &n, &m); for(i = 1; i <= n; i ++) {for(j = 1; j <= n; j ++){if(i == j){e[i][j] = 0;}else {e[i][j] = inf;} } }

３：用一個ｆｏｒ循環循環ｍ次，在這個循環里面，每次輸入兩個城市的標號以及它們之間的距離，并將表示這兩個城市之間的距離二維數組ｅ更新為新的距離（如果道路是單向的，只需更新一個ｅ；如果道路是雙向的，則需更新兩個ｅ，分別是城市ａ到城市ｂ的距離以及城市ｂ到城市ａ的距離）。

for(i = 1; i <= m; i ++) {scanf("%d%d%d", &a, &b, &c); if(c < e[a][b]) { e[a][b] = c; e[b][a] = c; } }

４：然后用三重循環，最外重循環從１到ｎ，表示要經歷的中轉點；第二層循環表示起始城市；最內層循環表示終止城市。在最內層循環內，用ｉｆ語句判斷從起始城市到終止城市的距離是否大于其經過中轉點的距離，如果是，則用兩個城市經過中轉點的距離代替從起始城市到終止城市的直接距離。

for(k = 1; k <= n; k ++) {for(i = 1; i <= n; i ++) { for(j = 1; j <= n; j ++) { if(e[i][j] > e[i][k] +e[k][j]) { e[i][j] = e[i][k] + e[k][j]; } } } }

５：輸出。輸出在二維數組ｅ中從城市ａ到城市ｂ的距離，即為其最短距離。

printf("%d\n", e[a][b]);

錯誤原因：此題錯了一次。
第一次：１.　輸入的問題。 沒有考慮清楚題目所說的任意兩個城市之間都可以有很多路徑。題目的這個描述其實就是說再輸入的時候如果兩個城市之間有大于１條以上的路徑，如果不進行判斷，后面的輸入就會覆蓋前面的輸入，導致輸入數據有誤。而我忽略了這一點，導致后面輸入的數據覆蓋了前面的數據。應該在輸入的時候進行判斷，因為此題是求任意兩個城市之間的最短距離，因此如果兩個城市之間的距離在進行輸入時，后面輸入的數據小于之前輸入的數據時，要更新兩個城市之間的距離，否則可以忽略此次輸入。

經驗總結：１：讀清楚題目，充分考慮題目所涵蓋的各種情況，尤其是對于“任意”這個詞，既包含了１到ｎ，也包含了１到２，２到３．．．．．．

2：要考慮城市標號是從0開始還是從1開始，這決定了for循環的起始標號。

我的ＡＣ代碼：

#include<stdio.h> #include<string.h>int main(void) {int e[202][202];int inf = 99999999;int n, m, i, j, k, t1, t2, t3, s, t;while(scanf("%d%d", &n, &m)!= EOF){ memset(e, 0, sizeof(e));for(i = 0; i <= n - 1; i ++){for(j = 0; j <= n - 1; j ++){if(i ==j){e[i][j] = 0;}else{e[i][j] = inf;}}}for(i = 1; i <= m; i ++){scanf("%d%d%d", &t1, &t2, &t3);{if(t3 < e[t1][t2]){e[t1][t2] =t3;e[t2][t1] =t3;}}}for(k = 0; k <= n- 1; k ++){for(i = 0; i <= n - 1; i ++){for(j = 0; j <= n- 1; j ++){if(e[i][j] > e[i][k] +e[k][j]){e[i][j] = e[i][k] + e[k][j];}}}}scanf("%d%d", &s, &t);if(e[s][t] != inf){printf("%d\n", e[s][t]);}else{printf("-1\n");}}return 0; }

轉載于:https://www.cnblogs.com/moon13579/p/8652705.html

總結

以上是生活随笔為你收集整理的航院 1874 畅通工程续的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。