#136. 最小瓶颈路

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

题目描述

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

输入格式

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

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

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

输出格式

输出包含 k k 行,每一行包含一个整数 p p p p 表示 s s 连接到 t t 的所有路径中单边长度最大值的最小值。另外,如果 s s t 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% 30\% 的数据 n100,m1000,k100,w1000 n \leq 100, m \leq 1000, k \leq 100, w \leq 1000
对于 70% 70\% 的数据 n1000,m10000,k1000,w100000 n \leq 1000, m \leq 10000, k \leq 1000, w \leq 100000
对于 100% 100\% 的数据 n1000,m100000,k1000,w10000000 n \leq 1000, m \leq 100000, k \leq 1000, w \leq 10000000
本题可能会有重边。
为了避免 Special Judge,本题所有的 w w 均不相同。