标题:
奶牛跨栏
标签:
图结构 最短路
详情:
Farmer John 想让她的奶牛准备郡级跳跃比赛，贝茜和她的伙伴们正在练习跨栏。她们很累，所以她们想消耗最少的能量来跨栏。 显...
| 标题: | 奶牛跨栏 | ||
| 标签: | 图结构 最短路 | ||
| 详情: | 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 行
接下来M行：每行包含三个整数 Si , Ei , Hi
接下来T 行：每行包含两个整数，表示任务i的起始站台和目标站台: Ai , Bi
|
||
| 输出格式: |
行 1..T: 行 i 为一个整数，表示任务i路径上最高的栏的高度的最小值。如果无法到达，输出 -1。
|
||
| 样例: |
|
#include <iostream>
using namespace std;
int a[301][301];
int inf=1000001;
int main(int argc, char *argv[]) {
int n,m,t;
cin>>n>>m>>t;
int p,q;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
a[i][j]=inf;
for(int i=1;i<=m;i++){
cin>>p>>q;
cin>>a[p][q];
}
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
//k为i，j经过的中间节点。
//x,y坐标相等的点为自身初始化的值。
if(i!=j && j!=k && i!=k){
a[i][j]=min(a[i][j],max(a[i][k],a[k][j]));
while(t--){
cin>>n>>m;
if(a[n][m]==inf)
cout<<\"-1\"<<endl;
else
cout<<a[n][m]<<endl;
}
return 0;
}
版权声明
本文仅代表作者观点，不代表百度立场。
本文系作者授权百度百家发表，未经许可，不得转载。
