poj 3615(floyd变形水题)

题意：求两点之间的所有路径中的最高点最低的路径的最高点。例如

1-> 2 12
3-> 2 8
1-> 3 5
则输出8。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 
 6 using namespace std;
 7 #define MAX(x,y) ((x)>(y)?(x):(y))
 8 #define MIN(x,y) ((x)>(y)?(y):(x))
 9 #define inf 0x7fffffff
10 #define MAXN 305
11 #define MAXM 25010
12 
13 int N,M,T;
14 int dis[MAXN][MAXN];
15 
16 void floyd()
17 {
18     for(int k=1;k<=N;k++)
19         for(int i=1;i<=N;i++)
20             for(int j=1;j<=N;j++)
21                 dis[i][j]=MIN(dis[i][j],MAX(dis[i][k],dis[k][j]));
22 }
23 
24 int main()
25 {
26     int s,e,h;
27     while(scanf("%d%d%d",&N,&M,&T) != EOF)
28     {
29         for(int i=1;i<=N;i++)
30             for(int j=1;j<=N;j++)
31                 if(i==j)
32                     dis[i][j]=0;
33                 else
34                     dis[i][j]=inf;
35         while(M--)
36         {
37             scanf("%d%d%d",&s,&e,&h);
38             dis[s][e]=h;
39         }
40         floyd();
41         while(T--)
42         {
43             scanf("%d%d",&s,&e);
44             if(dis[s][e]==inf)
45                 printf("-1\n");
46             else
47                 printf("%d\n",dis[s][e]);
48         }
49     }
50     return 0;
51 }

poj 3615(floyd变形 水题)

poj 3615(floyd变形水题)