Uvaoj 10048 - Audiophobia（Floyd算法變形）

 

 1 /*
 2    題目大意：
 3       從一個點到達另一個點有多條路徑，求這多條路經中最大噪音值的最小值！ 、
 4     
 5    思路：最多有100個點，然后又是多次查詢，想都不用想，Floyd算法走起！ 
 6 */
 7 #include<iostream>
 8 #include<cstring>
 9 #include<cstdio>
10 #define INF 0x3f3f3f3f
11 using namespace std;
12 
13 int map[105][105];
14 
15 int main(){
16    int n, m, q;
17    int u, v, d;
18    int cnt=0;
19    scanf("%d%d%d", &n, &m, &q);
20    while((n || m || q)){
21          memset(map, 0x3f, sizeof(map));
22       while(m--){
23          scanf("%d%d%d", &u, &v, &d);
24          map[u][v]=map[v][u]=d; 
25       }
26       for(int k=1; k<=n; ++k)
27          for(int i=1; i<=n; ++i)
28            for(int j=1; j<=n; ++j){
29              int dd=max(map[k][j], map[i][k]);
30              if(map[i][j] > dd)
31                 map[i][j] = dd; 
32            }
33       printf("Case #%d\n", ++cnt);
34       while(q--){
35          scanf("%d%d", &u, &v);
36          if(map[u][v]==INF)
37             printf("no path\n");
38          else
39             printf("%d\n", map[u][v]);
40       }
41       scanf("%d%d%d", &n, &m, &q);
42       if((n || m || q))
43          printf("\n");
44    } 
45    return 0;
46 }

轉載于:https://www.cnblogs.com/hujunzheng/p/3898468.html

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/news/531786.shtml
繁體地址，請注明出處：http://hk.pswp.cn/news/531786.shtml
英文地址，請注明出處：http://en.pswp.cn/news/531786.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！