#136. 最小瓶颈路

内存限制:128 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: Epicurus_

题目描述

给定一个包含 n 个节点和 m 条边的图,每条边有一个权值。
你的任务是回答 k 个询问,每个询问包含两个正整数 s t 表示起点和终点,要求寻找从 s t 的一条路径,使得路径上权值最大的一条边权值最小。

输入格式

第一行包含三个整数 n m k ,分别表示 n 个节点, m 条路径, k 个询问。

接下来 m 行,每行三个整数 u , v , w , 表示一个由 u v 的长度为 w 的双向边。

再接下来 k 行,每行两个整数 s , t ,表示询问从 s 连接到 t 的所有路径中单边长度最大值的最小值。

输出格式

输出包含 k 行,每一行包含一个整数 p p 表示 s 连接到 t 的所有路径中单边长度最大值的最小值。另外,如果 s t 没有路径相连通,输出 -1 即可。

样例

样例输入

8 11 3
1 2 10
2 5 50
3 4 60
7 5 60
3 6 30
1 5 30
6 7 20
1 7 70
2 3 20
3 5 40
2 6 90
1 7
2 8
6 2

样例输出

30
-1
30

数据范围与提示

对于 30\% 的数据 n \leq 100, m \leq 1000, k \leq 100, w \leq 1000
对于 70\% 的数据 n \leq 1000, m \leq 10000, k \leq 1000, w \leq 100000
对于 100\% 的数据 n \leq 1000, m \leq 100000, k \leq 1000, w \leq 10000000
本题可能会有重边。
为了避免 Special Judge,本题所有的 w 均不相同。