UVA10048 Audiophobia 解题报告

本文主要是介绍UVA10048 Audiophobia 解题报告，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接

https://vjudge.net/problem/UVA-10048

题目大意

输入一个C个点S条边（C≤100，S≤1000）的无向带权图，边权表示该路径上的噪声值。当噪声值太大时，耳膜可能会受到伤害，所以当你从某点去往另一个点时，总是希望路上经过的最大噪声值最小。输入一些询问，每次询问两个点，输出这两点间最大噪声值最小的路径（输出其最大噪声值即可）。

解题思路

对于任意一条至少包含两条边的路径i->j，考虑一个中间点k使得i->j的总长度等于i->k和k->j之和，此时已知路径i->k以及路径k->j各自的最大边权，那么显然i->j的最大边权是取他们的最大值。考虑不同的中间点k，结果可能不同，所以最后还需取一个最小值才是i->j的最佳路径（路径上的最大边权最小）。

代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
const int maxn = 1e3 + 10;
const int INF = 0x3fffffff;
const int mod = 1e9 + 7;
int G[maxn][maxn];
int n, m, q;void init() {for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++)G[i][j] = INF;
}void floyd() {for (int k = 1; k <= n; k++)for (int i = 1; i <= n; i++)for (int j = 1; j <= n; j++) {/*对于任意一条至少包含两条边的路径i->j，考虑一个中间点k使得i->j的总长度等于i->k和k->j之和，此时已知路径i->k以及路径k->j各自的最大边权，那么显然i->j的最大边权是取他们的最大值。考虑不同的中间点k，结果可能不同，所以最后还需取一个最小值才是i->j的最佳路径（路径上的最大边权最小）*/G[i][j] = min(G[i][j], max(G[i][k], G[k][j]));}
}void solve() {int kase = 0;while (cin >> n >> m >> q, n) {init();while (m--) {int u, v, w;cin >> u >> v >> w;G[u][v] = G[v][u] = w;}floyd();if (kase)cout << "\n";cout << "Case #" << ++kase << "\n";while (q--) {int u, v;cin >> u >> v;if (G[u][v] != INF)cout << G[u][v] << "\n";elsecout << "no path\n";}}
}int main() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cout << fixed;cout.precision(18);int Case = 1;// cin >> Case;while (Case--)solve();return 0;
}