P2888 [USACO07NOV] Cow Hurdles S

题目描述

Farmer John 想让她的奶牛准备郡级跳跃比赛，Bessie 和她的伙伴们正在练习跨栏。她们很累，所以她们想消耗最少的能量来跨栏。 显然，对于一头奶牛跳过几个矮栏是很容易的，但是高栏却很难。于是，奶牛们总是关心路径上最高的栏的高度。

奶牛的训练场中有 $N$ 个站台，分别标记为 $1,\dots,N$。所有站台之间有 $M$ 条单向路径，第 $i$ 条路经是从站台 $S_i$ 开始，到站台 $E_i$，其中最高的栏的高度为 $H_i$。无论如何跑，奶牛们都要跨栏。

奶牛们有 $T$ 个训练任务要完成。第 $i$ 个任务包含两个数字 $A_i$ 和 $B_i$，表示奶牛必须从站台 $A_i$ 跑到站台 $B_i$，可以路过别的站台。奶牛们想找一条路径从站台 $A_i$ 到站台 $B_i$，使路径上最高的栏的高度最小。 你的任务就是写一个程序，计算出路径上最高的栏的高度的最小值。

输入格式

第一行：三个空格隔开的整数 $N, M, T$。

接下来 $M$ 行：第 $i$ 行包含三个空格隔开的整数 $S_i, E_i, H_i$。

接下来 $T$ 行：第 $i$ 行包含两个空格隔开的整数，表示任务 $i$ 的起始站台和目标站台 $A_i, B_i$。

输出格式

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

输入输出样例 #1

输入 #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

输出 #1

4
8
-1

说明/提示

对于 $100\%$ 的数据，$1 \le N \le 300$，$1 \le M \le 2.5 \times 10^4$，$1 \le H_i \le 1 \times 10^6$，$1 \le T \le 4 \times 10^4$，$1 \le A_i,B_i \le N$。

感谢 @gaozhiyong @Cppsteve 提供翻译