最短路變型

1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cstdlib> 5 #include <algorithm> 6 #include <map> 7 using namespace std; 8 #define N 205 9 int g[N][N]; 10 map<string,int>mp; //map映射 11 int n,m; 12 13 void Floyd() //最短路變型 14 { 15 for(int k=0; k<n; k++) 16 { 17 for(int i=0; i<n; i++) 18 { 19 if(k==i||g[i][k]==-1) continue; 20 for(int j=0; j<n; j++) 21 { 22 if(k==j||g[k][j]==-1) continue; 23 g[i][j] = max(g[i][j],min(g[i][k],g[k][j])); 24 } 25 } 26 } 27 } 28 29 int main() 30 { 31 int cas = 1; 32 while(scanf("%d%d",&n,&m)!=EOF) 33 { 34 if(n==0&&m==0) break; 35 for(int i=0; i<n; i++) 36 for(int j=0; j<n; j++) 37 { 38 if(i==j) g[i][j] = 0; 39 else g[i][j] = -1; 40 } 41 string s1,s2; 42 int w; 43 mp.clear(); 44 int cnt=0,u,v; 45 for(int i=0; i<m;i++) 46 { 47 cin>>s1>>s2>>w; 48 if(mp.find(s1)==mp.end()) mp[s1] = cnt++; 49 u = mp[s1]; 50 if(mp.find(s2)==mp.end()) mp[s2] = cnt++; 51 v = mp[s2]; 52 g[u][v] = g[v][u] = w; 53 } 54 Floyd(); 55 cin>>s1>>s2; 56 printf("Scenario #%d\n",cas++); 57 printf("%d tons\n\n",g[mp[s1]][mp[s2]]); 58 } 59 return 0; 60 } View Code

?

轉載于:https://www.cnblogs.com/ar940507/p/3247227.html

總結

以上是生活随笔為你收集整理的POJ2263 ZOJ 1952的全部內容，希望文章能夠幫你解決所遇到的問題。

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