1604_最小瓶颈路

给定一个包含 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 的所有路径中单边长度最大值的最小值。

对于 30% 的数据 n ≤ 100, m ≤ 1000 ,k ≤ 100, w ≤ 1000

对于 70% 的数据 n ≤ 1000, m ≤ 10000, k ≤ 1000, w ≤ 100000

对于 100% 的数据 n ≤ 1000, m ≤ 100000, k ≤ 1000, w ≤ 10000000

本题可能会有重边。为了避免 Special Judge，本题所有的 w 均不相同。

输出包含 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