[最短路]USACO Nov07 Silver :Cow Hurdles 奶牛跨欄 hurdles 解題報告

奶牛跨欄

譯 by CmYkRgB123

描述

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，使路徑上最高的欄的高度最小。

你的任務就是寫一個程序，計算出路徑上最高的欄的高度的最小值。

輸入

* 行 1: 兩個整數 N, M, T

* 行 2..M+1: 行 i+1 包含三個整數 Si , Ei , Hi

* 行 M+2..M+T+1: 行 i+M+1 包含兩個整數，表示任務i的起始站臺和目標站臺: Ai , Bi

輸出

* 行 1..T: 行 i 爲一個整數，表示任務i路徑上最高的欄的高度的最小值。如果無法到達，輸出 -1。

輸入樣例

5 6 3

1 2 12

3 2 8

1 3 5

2 5 3

3 4 4

2 4 8

3 4

1 2

5 1

輸出樣例

4

8

-1 

【分析】

由題目描述可知，這是一個求最短路問題，由於是多源的，並且N最多只有300個，所以Floyd算法再合適不過了。

但是本題並不是單純的Floyd算法，需要把Floyd變形一下，每次求出Map[i][k]和Map[k][j]中的最大值，在與Map[i][j]比較，取小者賦給Map[i][j]。輸出用一個O(N^2)的枚舉找出最優解即可。

【我的代碼】

#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;

int Max(int a,int b)
{
    return a>b?a:b;
}

int mat[301][301];
int N,M,Q;

void Floyd()
{
    int temp;
    for (int k=1;k<=N;k++) 
    { 
        for(int i=1;i<=N;i++) 
                { 
                        for(int j=1;j<=N;j++) 
                        { 
                                if ( mat[i][k]!=-1 && mat[k][j]!=-1) 
                                   { 
                    temp=Max(mat[i][k],mat[k][j]);
                    if ( (mat[i][j]==-1) || ( mat[i][j]>temp ) ) 
                        mat[i][j]=temp; 
                                   } 
                                  } 
                } 
        } 
}

void init()
{
    scanf("%d %d %d\n",&N,&M,&Q);
   
    for (int i=1;i<=N;i++)
        for (int j=1;j<=N;j++)
            mat[i][j]=-1;
   
    for(int i=1;i<=N;i++)
        mat[i][i]=0;
   
    int a,b,c;
    for (int i=1;i<=M;i++)
    {
        scanf("%d %d %d\n",&a,&b,&c);
        mat[a][b]=c;
    }
    Floyd();
    for (int i=1;i<=Q;i++)
    {
        scanf("%d %d\n",&a,&b);
        printf("%d\n",mat[a][b]);
    }
    return;
}


int main()
{
    freopen("hurdles.in","r",stdin);
    freopen("hurdles.out","w",stdout);
    init();
    return 0;
}