UVa 10048 噪音恐惧症（Floyd）

题意

输入一个C个点S条边的无向带权图，边权表示该路径上的噪声值。输入一些询问，每次询问两个点，输出这两点间最大噪声值最小的路径。

思路

最简单的方法就是Floyd算法。本来是求长度的，现在求最大噪声值最小的路径，稍微改一下就好了。

d[i][j]=min(d[i][j],max(d[i][k],d[k][j]))

其次，也可以用Dijkstra算法来计算。

代码

 1 #include<iostream> 
 2 #include<cstring>
 3 #include<string>
 4 #include<algorithm>
 5 #include<vector>
 6 using namespace std;
 7 
 8 #define INF 1000001
 9 
10 int n, m, t;
11 int s, e;
12 
13 int map[105][105];
14 
15 
16 int main()
17 {
18     //freopen("D:\txt.txt", "r", stdin);
19     int kase = 1;
20     int a, b, w;
21     while (scanf("%d%d%d", &n, &m,&t))
22     {
23         if (m == 0 && n == 0 && t == 0)  break;
24         if (kase > 1)   printf("
");
25         printf("Case #%d
", kase++);
26 
27         for (int i = 1; i <= n; i++)
28         {
29             map[i][i] = INF;
30             for (int j = i + 1; j <= n; j++)
31                 map[i][j] = map[j][i] = INF;
32         }
33 
34         
35         for (int i = 0; i < m; i++)
36         {
37             scanf("%d%d%d", &a, &b, &w);
38             map[a][b] = map[b][a] = w;
39         }
40 
41         for (int k = 1; k <= n;k++)
42         for (int i = 1; i <= n;i++)
43         for (int j = 1; j <= n; j++)
44             map[i][j] = min(map[i][j], max(map[i][k], map[k][j]));
45 
46         for (int i = 0; i < t; i++)
47         {
48             scanf("%d%d", &s, &e);
49             if (map[s][e] == INF)   printf("no path
");
50             else  printf("%d
", map[s][e]);
51         }
52     }
53     return 0;
54 }

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<vector>
 4 #include<cstring>
 5 #include<queue>
 6 using namespace std;
 7 const int inf = 0x3f3f3f3f;
 8 typedef pair<int, int> pii;
 9 
10 int c, s, q;
11 vector<pii> g[105];
12 bool vis[105];
13 int d[105][105];
14 
15 struct HeapNode{
16     int d, u;
17     bool operator < (const HeapNode& rhs) const{
18         return d > rhs.d;
19     }
20 };
21 
22 
23 void dijkstra(int s){
24     memset(vis, 0, sizeof(vis));
25     for(int i=1; i<=c; i++)  d[s][i] = inf;
26     d[s][s] = 0;
27     priority_queue<HeapNode> Q;
28     Q.push((HeapNode){0, s});
29     while(!Q.empty()){
30         HeapNode x = Q.top(); Q.pop();
31         int u = x.u;
32         if(vis[u])  continue;
33         vis[u] = true;
34         for(int i=0; i<g[u].size(); i++){
35             int v = g[u][i].first;
36             if(d[s][v] > max(d[s][u], g[u][i].second)){
37                 d[s][v] = max(d[s][u], g[u][i].second);
38                 Q.push((HeapNode){d[s][v], v});
39             }
40         }
41     }
42 }
43 
44 int main(){
45     //freopen("in.txt", "r", stdin);
46     int cas = 1;
47     while(~scanf("%d%d%d", &c, &s, &q) && c && s && q){
48         for(int i=1; i<=c; i++)  g[i].clear();
49         if(cas > 1)  puts("");
50         printf("Case #%d
", cas++);
51         for(int i=0; i<s; i++){
52             int u, v, w;
53             scanf("%d%d%d", &u, &v, &w);
54             g[u].push_back(make_pair(v, w));
55             g[v].push_back(make_pair(u, w));
56         }
57         for(int i=1; i<=c; i++){
58             dijkstra(i);
59         }
60 
61         while(q--){
62             int st, ed;
63             scanf("%d%d", &st, &ed);
64             if(d[st][ed] == inf)  puts("no path");
65             else printf("%d
", d[st][ed]);
66         }
67     }
68     return 0;
69 }