POJ3615 Cow Hurdles【Floyd】

5 1

Source

USACO 2007 November Silver

题目大意：John想为农场的奶牛举办跳高比赛。奶牛们现在都累了，它们想尽可能的用最少的能量

完成跳高，因为跳过低点的障碍不是很困难，但是高点的障碍就非常困难，所以奶牛只关心它要越

过的障碍的最高高度。

现在给你N个点，编号为1~N，在N个点之间有M个障碍，给你M个障碍链接的点编号和障碍高度，

判断T组从点A跳到点B，尽可能使障碍高度低的路径上最高障碍物高度是多少。

思路：把障碍的高度看做是边，那么题目意思就是给你N个点，M个单向边。问点A到点B能达到的

最长边尽可能短的路径上最长边为多少。类似于求多源最短路径，用Floyd来做，更新最短路径距离

的时候改一下，变成求能达到的路径上最长边最小为多少。

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
const int MAXN = 330;
const int INF = 0xffffff0;
int Map[MAXN][MAXN],Dist[MAXN][MAXN];

void Floyd(int N)
{
    for(int i = 1; i <= N; ++i)
        for(int j = 1; j <= N; ++j)
            Dist[i][j] = Map[i][j];

    for(int k = 1; k <= N; ++k)
    {
        for(int i = 1; i <= N; ++i)
        {
            for(int j = 1; j <= N; ++j)
            {
                int tMax;   //这里边求的是能达到的路径上最长边最小为多少
                if(Dist[i][k] > Dist[k][j])
                    tMax = Dist[i][k];
                else
                    tMax = Dist[k][j];
                if(Dist[i][j] > tMax)
                    Dist[i][j] = tMax;
            }
        }
    }
}

int main()
{
    int N,M,T;
    while(~scanf("%d%d%d",&N,&M,&T))
    {
        for(int i = 1; i <= N; ++i)
            for(int j = 1; j <= N; ++j)
                    Map[i][j] = INF;
        for(int i = 1; i <= M; ++i)
        {
            int s,e,h;
            scanf("%d%d%d",&s,&e,&h);
            Map[s][e] = h;
        }
        Floyd(N);
        for(int i = 1; i <= T; ++i)
        {
            int a,b;
            scanf("%d%d",&a,&b);
            if(Dist[a][b] != INF)
                printf("%d\n",Dist[a][b]);
            else
                printf("-1\n");
        }
    }

    return 0;
}

POJ3615 Cow Hurdles【Floyd】

原文：http://blog.csdn.net/lianai911/article/details/43120951