[广义Floyd] UVA10048 噪音恐惧症 Audiophobia

噪音恐惧症 Audiophobia

题面翻译

题意描述

有一张有$C$个路口，$S$条街道的无向图，每条街道都一个噪音值。

请问从$c_1$走到$c_2$，经过的路径上最大噪音的最小值是多少。

输入格式

输入包含多组数据，每组数据第一行包含三个整数$C(\le 100),S(\le 1,000),Q(\le 10,000)$，分别表示路口数、街道数、询问数。

接下来$S$行，每行$3$个整数$c_1,c_2,d(c_1\ne c_2)$，分别表示一条街道连接的两个路口编号，以及这条街道噪音的分贝值。

接下来$Q$行，每行给定两个路口编号$c_1,c_2(c_1\ne c_2)$，请你输出这两个路口之间路径的最大分贝值的最小值。如果$c_1$不能到达$c_2$，输出"no path"。

输入以$C=S=Q=0$结束。

输出格式

每组数据前输出一行数据组数的编号。（见样例）

对于每个询问，输出一行。

每两组数据之间输出一个空行。

题目描述

PDF

输入格式

输出格式

样例 #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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

样例输出 #1

Case #1
80
60
60

Case #2
40
no path
80
1
2
3
4
5
6
7
8
9

分析

这道题可以用Floyd来做。
我们只用求通过两点边权最小的路径，这个边权每条边独立的，不累加，所以改一下模板即可~

代码

#include

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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67