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 }

 

上一篇:uva oj 567 - Risk(Floyd算法)


下一篇:重学计算机组成原理(五)- "旋转跳跃"的指令实现(上)