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 = 305;
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 = 1; i <= m; i++)
        for (int j = 1; j <= m; j++)
            dist[i][j] = INF;
    for (int i = 0; i < n; i++)
    {
        int from, to, cost;
        scanf("%d%d%d", &from, &to, &cost);
        dist[from][to] = cost;
    }
    for(int i = 1; i <= m; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            for (int k = 1; 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 = 0; i < k; i++)
    {
        int from, to;
        scanf("%d%d", &from, &to);
        if (dist[from][to] == INF) cout << -1 << endl;
        else  cout << dist[from][to] << endl;
    }
    return 0;
}