題目鏈接 https://vjudge.net/problem/UVA-10048

【題意】
輸入一個C個點，S個邊（C<=100,S<=1000）的無向圖，邊權表示該路徑上的噪聲值，當你從某點出發到另外一點時希望路上經過的最大噪聲值最小，輸入一些詢問，每次詢問兩個點，輸出這兩點最大噪聲值最小的路徑。

【思路】
floyd算法的變型，只要設d[i][j]為從i出發，到j的最大噪聲最小值，那么按照floyd算法,d[i][j]=min(d[i][j],max(d[i][k],d[k][j]))，遞推即可。

#include<bits/stdc++.h>
using namespace std;const int inf = 100050;
const int maxn = 150;int n, m, q;
int g[maxn][maxn];
int d[maxn][maxn];void init() {for (int i = 1; i <= n; ++i) for (int j = 1; j <= n; ++j)g[i][j] = i == j ? 0 : inf;
}void floyd() {memcpy(d, g, sizeof(d));for (int k = 1; k <= n; ++k) {for (int i = 1; i <= n; ++i) {for (int j = 1; j <= n; ++j) {d[i][j] = min(d[i][j], max(d[i][k], d[k][j]));}}}
}int main() {int kase = 0;while (scanf("%d%d%d", &n, &m, &q) == 3) {if (!n && !m && !q) break;if (kase) printf("\n");init();for (int i = 1; i <= m; ++i) {int u, v, c;scanf("%d%d%d", &u, &v, &c);g[u][v] = g[v][u] = c;}floyd();printf("Case #%d\n", ++kase);while (q--) {int u, v;scanf("%d%d", &u, &v);if (d[u][v] != inf) printf("%d\n", d[u][v]);else printf("no path\n");}}return 0;
}

轉載于:https://www.cnblogs.com/wafish/p/10465428.html

總結

以上是生活随笔為你收集整理的Uva 10048 - Audiophobia （Floyd变形）的全部內容，希望文章能夠幫你解決所遇到的問題。

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