【uva 10048】Audiophobia（图论--Floyd算法）

题意：有一个N点M边的无向带权图，边权表示路径上的噪声值。有Q个询问，输出 x,y 两点间的最大噪声值最小的路径的该值。(N≤100,M≤1000,Q≤10000)

解法：N值小，且问多对点之间的路径，用Floyd算法就可以搞定了~o(〃'▽'〃)o

 1 #include<cstdio>
 2 #include<cstdlib>
 3 #include<cstring>
 4 #include<iostream>
 5 using namespace std;
 6 
 7 const int N=110,M=1010,Q=10010,INF=(int)2e9;
 8 int n,m,q;
 9 int d[N][N];
10 
11 int mmin(int x,int y) {return x<y?x:y;}
12 int mmax(int x,int y) {return x>y?x:y;}
13 int main()
14 {
15     int T=0;
16     while (1)
17     {
18       scanf("%d%d%d",&n,&m,&q);
19       if (!n && !m && !q) break;
20       for (int i=1;i<=n;i++)
21        for (int j=1;j<=n;j++)
22          d[i][j]=INF;
23       int x,y,w;
24       for (int i=1;i<=m;i++)
25       {
26         scanf("%d%d%d",&x,&y,&w);
27         d[x][y]=d[y][x]=w;
28       }
29       for (int k=1;k<=n;k++)
30        for (int i=1;i<=n;i++)
31         for (int j=1;j<=n;j++)
32           d[i][j]=mmin(d[i][j],mmax(d[i][k],d[k][j]));
33       if (T) printf("
");
34       printf("Case #%d
",++T);
35       for (int i=1;i<=q;i++)
36       {
37         scanf("%d%d",&x,&y);
38         if (d[x][y]==INF) printf("no path
");
39         else printf("%d
",d[x][y]);
40       }
41     }
42     return 0;
43 }