題目鏈接：https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=989

紫書P365頁

題意：求最大值的最小值。

莫名其妙的WA，原來是INF的值太大，還是劉汝佳說的好，INF太大d[i][k]+d[k][j]，就容易溢出，稍微大一點就好，就是總長。

然后就是重邊的問題了，題目死活沒找到有說到重邊的問題。還好經驗告訴我，有重邊。

然后就是PE，還是很隱蔽。

#include <cstdio> #include <cstring> #include <algorithm>using namespace std;#define MAXN 105 #define INF 1000000000int dist[MAXN][MAXN];int main() {int n,m,q;int cases = 0;while(scanf("%d%d%d",&n,&m,&q)==3&&n){for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)dist[i][j] = INF;for(int i=1;i<=n;i++)dist[i][i] = 0;for(int i=0;i<m;i++){int u,v,d;scanf("%d%d%d",&u,&v,&d);dist[u][v] = dist[v][u] = min(dist[u][v],d);}for(int k=1;k<=n;k++)for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)dist[i][j] = min(dist[i][j],max(dist[i][k],dist[k][j]));if(cases) puts("");printf("Case #%d\n",++cases);for(int i=0;i<q;i++){int u,v;scanf("%d%d",&u,&v);if(dist[u][v]>=INF)puts("no path");else printf("%d\n",dist[u][v]);}}return 0; }

?

轉載于:https://www.cnblogs.com/TreeDream/p/5788356.html

總結

以上是生活随笔為你收集整理的Uva(10048)，最短路Floyd的全部內容，希望文章能夠幫你解決所遇到的問題。

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