首页 > 代码库 > UVa 10048 (Floyd变形) Audiophobia

UVa 10048 (Floyd变形) Audiophobia

2024-10-24 15:59:39   212人阅读

题意：

给一个带权无向图，和一些询问，每次询问两个点之间最大权的最小路径。

分析：

紫书上的题解是错误的，应该是把原算法中的加号变成max即可。但推理过程还是类似的，如果理解了Floyd算法的话，这个应该也很容易理解。

技术分享
 1 #include <cstdio> 2 #include <algorithm> 3 using namespace std; 4  5 const int maxn = 100 + 10; 6 const int INF = 1000000000; 7 int d[maxn][maxn]; 8  9 int main()10 {11     //freopen("in.txt", "r", stdin);12     int kase = 0, n, m, q;13     while(scanf("%d%d%d", &n, &m, &q) == 3 && n)14     {15         for(int i = 0; i < n; ++i)16         {17             d[i][i] = 0;18             for(int j = i+1; j < n; ++j)19                 d[i][j] = d[j][i] = INF;20         }21 22         for(int i = 0; i < m; ++i)23         {24             int u, v, w;25             scanf("%d%d%d", &u, &v, &w);26             u--, v--;27             d[u][v] = d[v][u] = w;28         }29 30         for(int k = 0; k < n; ++k)31             for(int i = 0; i < n; ++i)32                 for(int j = 0; j < n; ++j)33                     if(d[i][k] < INF && d[k][j] < INF)34                         d[i][j] = min(d[i][j], max(d[i][k], d[k][j]));35 36         if(kase) printf("\n");37         printf("Case #%d\n", ++kase);38         while(q--)39         {40             int u, v;41             scanf("%d%d", &u, &v);42             u--, v--;43             if(d[u][v] == INF) puts("no path");44             else printf("%d\n", d[u][v]);45         }46     }47 48     return 0;49 }
代码君

 

UVa 10048 (Floyd变形) Audiophobia


联系
我们