a674 - 10048 - Audiophobia
題目描述
題目描述一個城市地圖，其中路口由街道連接，每條街道都有一個噪音值。目標是找到從一個路口到另一個路口的路徑，使得路徑上遇到的最大噪音最小。如果不存在路徑，則輸出 "no path"。
解題思路
這題可以使用 Floyd-Warshall 演算法來解決。Floyd-Warshall 演算法可以找到圖中所有頂點對之間的最短路徑。在這裡，"最短路徑"指的是最大噪音最小的路徑。
- 初始化: 建立一個鄰接矩陣
ans，表示每個路口之間的噪音值。如果兩個路口之間沒有直接連接，則將其初始化為一個很大的值（例如 100000000）。對角線元素初始化為 0。 - 讀取輸入: 讀取街道的資訊，並更新鄰接矩陣。
- Floyd-Warshall 演算法: 使用三重迴圈迭代所有可能的中間頂點
k，以及所有可能的起點i和終點j。如果通過頂點k從i到j的路徑比目前已知的路徑更好（即最大噪音更小），則更新ans[i][j]。 - 查詢: 對於每個查詢，檢查
ans[x][y]的值。如果該值仍然是初始化的最大值，則表示不存在路徑，輸出 "no path"。否則，輸出ans[x][y]。
複雜度分析
- 時間複雜度: O(C^3)，其中 C 是路口的數量。Floyd-Warshall 演算法的時間複雜度為 O(V^3)，其中 V 是頂點數。
- 空間複雜度: O(C^2)，用於儲存鄰接矩陣。
程式碼
#include <iostream>
using namespace std;
int ans[101][101],c,s,q,x,y,v,ca,st;
int main(){
cin.tie(0); ios::sync_with_stdio(false);
while(cin >> c >> s >> q){
if(!c&&!s&&!q)break;
for(int i=1;i<=c;++i)
for(int j=1;j<=c;++j){
if(i==j)ans[i][j]=0;
else ans[i][j]=100000000;
}
while(s--){
cin >> x >> y >> v;
ans[x][y]=min(ans[x][y],v);
ans[y][x]=min(ans[y][x],v);
}
for(int k=1;k<=c;++k)
for(int i=1;i<=c;++i)
for(int j=1;j<=c;++j)
if(ans[i][j]>max(ans[i][k],ans[k][j]))
ans[i][j]=max(ans[i][k],ans[k][j]);
if(st)cout << "\n";
st=1;
cout << "Case #" << ++ca << "\n";
while(q--){
cin >> x >> y;
if(ans[x][y]==100000000){
cout << "no path\n";
}
else{
cout << ans[x][y] << "\n";
}
}
}
}