UVA 10048 Audiophobia 任意两点的路径上最大的边

题目是要求任意给定两点的的路径上最大的边，最终输出这些最大边中最小的值，也就是求一条路径使得这条路径上最大的边在所有连通两点的路径中最短。
根据Floyd—Warshall算法改造一下就行了。dp[i][j]表示i，j两点的连通路径中最大边的最小值。

 1 #include<stdio.h>
 2 #include<string.h>
 3 #define N 110
 4 #define INF 999999999
 5 #define max(a,b)  ((a)>(b)?(a):(b))
 6 #define min(a,b)  ((a)>(b)?(b):(a))
 7 
 8 int dp[N][N];
 9 int main(void)
10 {
11     int ct=0,c,s,q;
12     int i,j,k,a,b,d;
13 
14     while(scanf("%d%d%d",&c,&s,&q)&&(c||s||q))
15     {
16         ct++;
17         if(ct!=1)
18             puts("");
19             printf("Case #%d
",ct);
20         memset(dp,0,sizeof(dp));
21         while(s--)
22         {
23 
24             scanf("%d%d%d",&a,&b,&d);
25             dp[a][b]=dp[b][a]=d;
26         }
27         for(i=1; i<N; i++)
28             for(j=1; j<N; j++)
29                 if(i-j)
30                     if(!dp[i][j])
31                         dp[i][j]=INF;
32         int temp;
33         for(k=1; k<=c; k++)
34             for(i=1; i<=c; i++)
35                 for(j=1; j<=c; j++)
36                 {
37                     temp=max(dp[i][k],dp[k][j]);/*求i和k，k和j连通路径最大边中较大的值。*/
38                          dp[i][j]=min(temp,dp[i][j]);/*将得到的较大值和原来的dp[i][j]进行比较取较小的值更新dp[i][j]*/
39                 }
40         while(q--)
41         {
42             scanf("%d%d",&a,&b);
43             if(dp[a][b]==INF)
44                 puts("no path");
45             else
46             printf("%d
",dp[a][b]);
47         }
48     }
49     return 0;
50 }