更加深入的了解Floyd
下面來看一道簡單的但是有點意思
的最短路徑的問題。本次用的解法
是Floyd.
題目：http://acm.swust.edu.cn/oj/problem/0819/
在使用Floyd的時候有三點需要注意：
一：map[][]數組的初始化
這個是十分的重要的，不然無法Floyd。具體點就是，map[i][i]=0; map[i][j]=INF;
二、輸入時候的選擇性
只有做到這一步，才能保證是最短的，不然不行。具體點就是，if(map[u][v] > w) map[u][v] = map[v][u] = w;
這個主要用在題目中沒有說明是否會多次輸入同一條邊的時候。
三、只有一個結點的情況
毫無疑問輸出結果就是0了，但是一定要把這個給特判一下。不然Wrong。
好了， 不說了， 具體的還是看代碼要好點。
View Code
#include "iostream" using namespace std; #define eMax 505 #define nMax 105 #define INF 99999999 struct edge { int fir, sec; }e[eMax]; int map[nMax][nMax]; int n, m; void Floyd() { for(int k=1; k<=n; k++) for(int i=1; i<=n; i++) for(int j=1; j<=n; j++) map[i][j] = min(map[i][j], map[i][k]+map[k][j]); } int main() { int u, v, w, k; while(cin>>n>>m) { k = 0; for(int i=1; i<=n; i++){ //map數組的初始化 for(int j=1; j<=n; j++){ if(i==j) map[i][j] = 0; else map[i][j] = INF; } } for(int i=0; i<m; i++){ //輸入時的處理 cin>>u>>v>>w; if(map[u][v] > w){ map[u][v] = map[v][u]= w; e[k].fir = u; e[k++].sec = v; } } Floyd(); int Min = INF; for(int i=0; i<k; i++) { u = e[i].fir; v = e[i].sec; Min = min(Min, map[1][u]+map[v][n]); Min = min(Min, map[1][v]+map[u][n]); } if(n==1) cout<<"0"<<endl; else if(Min < INF) cout<<Min<<endl; else cout<<"-1"<<endl; } }
posted on 2011-11-26 10:46 More study needed. 閱讀(259) 評論(0) 收藏 舉報
浙公網安備 33010602011771號