[BZOJ1641]&&[Usaco2007 Nov]Cow Hurdles 奶牛跨栏

描述 Description

Farmer John 想让她的奶牛准备郡级跳跃比赛,贝茜和她的伙伴们正在练习跨栏。她们很累,所以她们想消耗最少的能量来跨栏。 显然,对于一头奶牛跳过几个矮栏是很容易的,但是高栏却很难。于是,奶牛们总是关心路径上最高的栏的高度。 奶牛的训练场中有 N (1 ≤ N ≤ 300) 个站台,分别标记为 1..N。所有站台之间有 M (1 ≤ M ≤ 25,000) 条单向路径,第 i 条路经是从站台 Si 开始,到站台 Ei,其中最高的栏的高度为 Hi (1 ≤ Hi ≤ 1,000,000)。无论如何跑,奶牛们都要跨栏。 奶牛们有 T (1 ≤ T ≤ 40,000) 个训练任务要完成。第 i 个任务包含两个数字 Ai 和 Bi (1 ≤ Ai ≤ N; 1 ≤ Bi ≤ N),表示奶牛必须从站台 Ai 跑到站台 Bi,可以路过别的站台。奶牛们想找一条路径从站台 Ai 到站台 Bi,使路径上最高的栏的高度最小。 你的任务就是写一个程序,计算出路径上最高的栏的高度的最小值。

输入格式 InputFormat

行 1: 两个整数 N, M, T.

行 2..M+1: 行 i+1 包含三个整数 Si , Ei , Hi.

行 M+2..M+T+1: 行 i+M+1 包含两个整数,表示任务 i 的起始站台和目标站台: Ai , Bi.

输出格式 OutputFormat

行 1..T: 行 i 为一个整数,表示任务 i 路径上最高的栏的高度的最小值。如果无法到达,输出 -1。

样例输入 SampleInput

5 15 15
1 3 622809
1 5 229876
5 2 442313
2 5 727278
1 4 977609
4 2 227894
3 5 903365
3 4 68582
4 1 72258
3 2 335607
4 5 140864
3 1 469688
1 2 161242
4 3 12301
2 3 52120
5 1
2 3
4 1
3 4
2 1
1 2
5 2
5 3
1 5
4 2
3 2
3 1
1 4
3 5
4 3

样例输出 SampleOutput

442313
52120
72258
68582
72258
161242
442313
442313
161242
161242
161242
72258
161242
140864
12301

来源 Source

Silver


BZOJ 1641


代码 Code

Floyd.

#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int inf=0x7fffffff/27.11;
int a[305][305];
int i,j,t,n,m,l,r,k,z,y,x;
inline int read()
{
    int x=0;char ch=getchar();
    while (ch<'0' || ch>'9') ch=getchar();
    while (ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();
    return x;
}
int main()
{
    n=read();m=read();t=read();
    for (i=1;i<=n;i++) for (j=1;j<=n;j++) a[i][j]=inf;
    for (i=1;i<=m;i++)
    {
        x=read();y=read();z=read();
        a[x][y]=min(a[x][y],z);
    }
    for (k=1;k<=n;k++) for (i=1;i<=n;i++) for (j=1;j<=n;j++) if (a[i][k]!=inf && a[k][j]!=inf)
    {
        a[i][j]=min(a[i][j],max(a[i][k],a[k][j]));
    }
    for (i=1;i<=t;i++)
    {
        x=read();y=read();
        if (a[x][y]==inf) printf("-1n");
        else printf("%d\n",a[x][y]);
    }
    return 0;
}