USACO NOV07 Silver Cow Hurdles 奶牛跨欄
本文正體字版由OpenCC轉換
根據題意構圖，求每次兩點間路徑上最大值的最小值。可以使用變形的Floyd算法，因爲有多次詢問。
#include <iostream>
#define INF 0x7FFFFFF
#define MAX 301
using namespace std;
int N,M,T;
int dis[MAX][MAX];
void init()
{
int i,j,a,b,v;
freopen("hurdles.in","r",stdin);
freopen("hurdles.out","w",stdout);
cin >> N >> M >> T;
for (i=1;i<=N;i++)
{
for (j=1;j<=N;j++)
dis[i][j]=INF;
dis[i][i]=0;
}
for (i=1;i<=M;i++)
{
scanf("%d%d%d",&a,&b,&v);
dis[a][b]=v;
}
}
void floyed_minmax() //路徑上最大值最小
{
int i,j,k,max;
for (k=1;k<=N;k++)
{
for (i=1;i<=N;i++)
{
for (j=1;j<=N;j++)
{
if (dis[i][k]>dis[k][j])
max=dis[i][k];
else
max=dis[k][j];
if (max<dis[i][j])
dis[i][j]=max;
}
}
}
}
int main()
{
int i,a,b;
init();
floyed_minmax();
for (i=1;i<=T;i++)
{
scanf("%d%d",&a,&b);
if (dis[a][b]==INF)
dis[a][b]=-1;
printf("%dn",dis[a][b]);
}
return 0;
}
奶牛跨欄
譯 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
上次修改時間 2017-02-03