UVa10048 Audiophobia(floyd)

题意

给出一个图，图中的边表示从点u到点v路径上的噪音。给出q个查询，问从u到v所经路径上的最小噪音

思路

在使用floyd计算点对之间的路径时， D u , v k = m i n { D u , v k − 1 , m a x { D u , k k − 1 , D k , v k − 1 } } D_{u, v}^k= min \{D_{u, v}^{k - 1}, max\{D_{u, k}^{k- 1}, D_{k, v}^{k - 1}\}\} Du,vk​=min{Du,vk−1​,max{Du,kk−1​,Dk,vk−1​}}
代码如下

#include <bits/stdc++.h>using namespace std;#define _for(i, a, b) for(int i = (a); i < (b); i++)
#define _rep(i, a, b) for (int i = (a); i <= (b); i++)const int N = 104;
const int INF = 1e9;int graph[N][N];void fastio()
{ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
}int main()
{fastio();#ifndef ONLINE_JUDGEifstream fin("f:\\OJ\\uva_in.txt");streambuf* back = cin.rdbuf(fin.rdbuf());#endifint kase = 1;int c, s, q;while (cin >> c >> s >> q) {if (c == 0 && s == 0 && q == 0) {break;}if (kase > 1) {cout << endl;}cout << "Case #" << kase++ << endl;_for(i, 0, c) {_for (j, 0, c) {graph[i][j] = (i == j) ? 0 : INF;}}_for(i, 0, s) {int c1, c2, d;cin >> c1 >> c2 >> d;--c1;--c2;graph[c1][c2] = min(graph[c1][c2], d);graph[c2][c1] = graph[c1][c2];}_for(k, 0, c) {_for(i, 0, c) {_for(j, 0, c) {if (graph[i][k] != INF && graph[k][j] != INF) {graph[i][j] = min(graph[i][j], max(graph[i][k], graph[k][j]));}}}}_for(i, 0, q) {int c1, c2;cin >> c1 >> c2;--c1;--c2;int ans = graph[c1][c2];if (ans == INF) {cout << "no path" << endl;} else {cout << ans << endl;}}}#ifndef ONLINE_JUDGEcin.rdbuf(back);#endifreturn 0;
}