POJ 3615 Cow Hurdles

http://poj.org/problem?id=3615

floyd 最短路径的变形 dist[i][j]变化为 : i j之间的最大边

那么输入的时候可以直接把dist[i][j] 当作i j 之间的边进行输入

转移方程 dist[i][j] = max(dist[i][j], min(dist[i][k], dist[k][j]))

 #include <iostream>

 #include <string.h>

 #include <stdio.h>

 #define INF 0x3fffffff

 using namespace std;

 const int maxn = ;

 int Map[maxn][maxn];

 int dist[maxn][maxn];//dist[i][j]表示 i 到 j 的最大边是多少？

 //转移方程 dist[i][j] = min( dist[i][j] ,max(dist[i][k], dist[k][j])) ---> "**"

 //

 //与floyd的区别 dist是 i-j的最短'距离'

 int main()

 {

     int m, n, k;

     scanf("%d%d%d", &m, &n, &k);

     for(int i = ; i <= m; i++)

         for (int j = ; j <= m; j++)

             dist[i][j] = INF;

     for (int i = ; i < n; i++)

     {

         int from, to, cost;

         scanf("%d%d%d", &from, &to, &cost);

         dist[from][to] = cost;

     }

     for(int i = ; i <= m; i++)

     {

         for (int j = ; j <= m; j++)

         {

             for (int k = ; k <= m; k++)

             {

                // if (dist[j][k] == -1) dist[j][k] = max(dist[j][i], dist[i][k]);

                 //else

                     dist[j][k] = min(dist[j][k], max(dist[j][i], dist[i][k]));

             }

         }

     }

     for (int i = ; i < k; i++)

     {

         int from, to;

         scanf("%d%d", &from, &to);

         if (dist[from][to] == INF) cout << - << endl;

         else  cout << dist[from][to] << endl;

     }

     return ;

 }