#136. 最小瓶颈路

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

题目描述

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

输入格式

第一行包含三个整数 nnmmkk,分别表示 nn 个节点, mm 条路径, kk 个询问。

接下来 mm 行,每行三个整数 uu , vv , ww, 表示一个由 uuvv 的长度为 ww 的双向边。

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

输出格式

输出包含 kk 行,每一行包含一个整数 pppp 表示 ss 连接到 tt 的所有路径中单边长度最大值的最小值。另外,如果 sstt 没有路径相连通,输出 -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,w1000n \leq 100, m \leq 1000, k \leq 100, w \leq 1000
对于 70%70\% 的数据 n1000,m10000,k1000,w100000n \leq 1000, m \leq 10000, k \leq 1000, w \leq 100000
对于 100%100\% 的数据 n1000,m100000,k1000,w10000000n \leq 1000, m \leq 100000, k \leq 1000, w \leq 10000000
本题可能会有重边。
为了避免 Special Judge,本题所有的 ww 均不相同。