#P2888. [USACO07NOV] 奶牛栏
[USACO07NOV] 奶牛栏
题目描述
Farmer John 想让她的奶牛准备郡级跳跃比赛,Bessie 和她的伙伴们正在练习跨栏。她们很累,所以她们想消耗最少的能量来跨栏。 显然,对于一头奶牛跳过几个矮栏是很容易的,但是高栏却很难。于是,奶牛们总是关心路径上最高的栏的高度。
奶牛的训练场中有 个站台,分别标记为 。所有站台之间有 条单向路径,第 条路经是从站台 开始,到站台 ,其中最高的栏的高度为 。无论如何跑,奶牛们都要跨栏。
奶牛们有 个训练任务要完成。第 个任务包含两个数字 和 ,表示奶牛必须从站台 跑到站台 ,可以路过别的站台。奶牛们想找一条路径从站台 到站台 ,使路径上最高的栏的高度最小。 你的任务就是写一个程序,计算出路径上最高的栏的高度的最小值。
输入格式
第一行:三个空格隔开的整数 。
接下来 行:第 行包含三个空格隔开的整数 。
接下来 行:第 行包含两个空格隔开的整数,表示任务 的起始站台和目标站台 。
输出格式
行:第 行为一个整数,表示任务 路径上最高的栏的高度的最小值。如果无法到达,输出 -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
提示
对于 的数据,,,,,。