3914: 最小瓶颈路
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：0
解决：0
题目描述
给定一个包含 $ 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 $ 均不相同。