MYF

UVa 10048 Audiophobia

Posted on | In | | Visitors

题目链接

UVa 10048

方法：最短路变形

题目分析

题目大意

给定n个城市，m条街道，q次询问。每一条边表示表示该街的声音大小，q次讯问，每次给定两个城市u,v，问从u到v他需要最少忍耐多少db的音量

解析

q次讯问，多源多终点，找一条路径，所以直接Floyd处理一下就好了，不过要注意一下floyd里的那个表达式

代码

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
#include <set>
#include <map>
#include <stack>
#include <cmath>
#include <queue>
#include <cstdio>
#include <string>
#include <vector>
#include <iomanip>
#include <cstring>
#include <iostream>
#include <algorithm>
#define PI acos(-1)
#define debug         printf("Hi----------\n")
#define eps 1e-8
#define INF 0x3f3f3f3f
#pragma comment(linker, "/STACK:1024000000,1024000000")
typedef long long ll;
using namespace std;
#define maxn 10005
int mp[105][105];
int main(){
    bool flag=false;
    int cas=0,c,s,q,u,v,w;
    while (scanf("%d%d%d",&c,&s,&q),c) {
        if (flag) printf("\n");
        memset(mp, INF, sizeof(mp));
        
        for (int i=1; i<=s; i++) {
            scanf("%d%d%d",&u,&v,&w);
            mp[u][v]=w;
            mp[v][u]=w;
        }
        
        for (int k=1; k<=c; k++) {
            for (int i=1; i<=c; i++) {
                for (int j=1; j<=c; j++) {
                    //从i到j城市，有两种途径，一种是直接从i到j，一种是i->k->j，i到j就是mp[i][j]，而i->k->j是mp[i][k]和mp[k][j]两者中的最大值
                    mp[i][j]=min(mp[i][j], max(mp[i][k], mp[k][j]));
                }
            }
        }
        
        printf("Case #%d\n",++cas);
        
        for (int i=1; i<=q; i++) {
            scanf("%d%d",&u,&v);
            if (mp[u][v]==INF)
                printf("no path\n");
            else
                printf("%d\n",mp[u][v]);
        }
        
        flag=true;
    }
}