[广义Floyd] UVA10048 噪音恐惧症 Audiophobia
噪音恐惧症 Audiophobia
题面翻译
题意描述
有一张有 C C C个路口， S S S条街道的无向图，每条街道都一个噪音值。
请问从 c 1 c_1 c1走到 c 2 c_2 c2，经过的路径上最大噪音的最小值是多少。
输入格式
输入包含多组数据，每组数据第一行包含三个整数 C ( ≤ 100 ) , S ( ≤ 1 , 000 ) , Q ( ≤ 10 , 000 ) C(\leq 100),S(\leq1,000),Q(\leq 10,000) C(≤100),S(≤1,000),Q(≤10,000)，分别表示路口数、街道数、询问数。
接下来 S S S行，每行 3 3 3个整数 c 1 , c 2 , d ( c 1 ≠ c 2 ) c_1,c_2,d(c_1≠c_2) c1,c2,d(c1=c2)，分别表示一条街道连接的两个路口编号，以及这条街道噪音的分贝值。
接下来 Q Q Q行，每行给定两个路口编号 c 1 , c 2 ( c 1 ≠ c 2 ) c_1,c_2(c_1 ≠ c_2) c1,c2(c1=c2)，请你输出这两个路口之间路径的最大分贝值的最小值。如果 c 1 c_1 c1不能到达 c 2 c_2 c2，输出"no path"。
输入以 C = S = Q = 0 C=S=Q=0 C=S=Q=0结束。
输出格式
每组数据前输出一行数据组数的编号。（见样例）
对于每个询问，输出一行。
每两组数据之间输出一个空行。
题目描述
输入格式
输出格式
样例 #1
样例输入 #1
7 9 3
1 2 50
1 3 60
2 4 120
2 5 90
3 6 50
4 6 80
4 7 70
5 7 40
6 7 140
1 7
2 6
6 2
7 6 3
1 2 50
1 3 60
2 4 120
3 6 50
4 6 80
5 7 40
7 5
1 7
2 4
0 0 0
样例输出 #1
Case #1
80
60
60
Case #2
40
no path
80
分析
这道题可以用Floyd来做。
我们只用求通过两点边权最小的路径，这个边权每条边独立的，不累加，所以改一下模板即可~
代码
#include<bits/stdc++.h>
using namespace std;
const int inf=0x3f3f3f3f;
int f[1000][1000];
int n,m,q;
int ka;
int main()
{
while(scanf("%d%d%d",&n,&m,&q)==3)
{
if(n==0)
{
break;
}
memset(f,inf,sizeof(f));
int s,k,d;
while(m--)
{
cin>>s>>k>>d;
f[s][k]=f[k][s]=d;
}
for(int ii=1;ii<=n;ii++)//Floyd模板
{
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
f[i][j]=min(f[i][j],max(f[i][ii],f[ii][j]));//改一下这里
}
}
}
if(ka>0)
{
cout<<endl;
}
printf("Case #%d\n",++ka);
while(q--)
{
cin>>s>>k;
if(f[s][k]==inf)
{
cout<<"no path\n";
}
else
{
cout<<f[s][k]<<endl;
}
}
}
return 0;
}