14115: 【原4115】mst
题目
题目描述
author: Lmxyy 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4115
Description
虽然xyy没选“图论与组合”这门课，但是xyy还是很喜欢图论的。
最近xyy正在研究一个图论问题。他现在有一张无向边带权图\(G(V,E)\)，它规定该图上的每条简单路径的权值为所经过的边权中次大值。
现在，xyy需要知道给定两个点\(A\)和\(B\)，所有从\(A\)到\(B\)的简单路径中，最小的权值是什么。但是随着问题越来越多，他就只有想你寻求帮助。
注：
- 如果路径上的各顶点均不互相重复，称这样的路径为简单路径。
- 若一条简单路径上的边权为\(1,2,2\)，其权值为\(2\)。
- 对于长度为\(1\)的简单路径，我们定义其权值为\(0\)。
Input Format
第一行三个正整数\(N,M,Q\)，分别表示点数、边数以及询问个数。
接下来\(M\)行，每行三个正整数\(x,y,v\)，表示\(x\)点到\(y\)连接了一条边权为\(v\)的无向边。
再接下来\(Q\)行，每行两个正整数\(A,B\)，表示一组询问。
Output Format
对于每组询问，输出一行一个整数，表示答案。
若\(A,B\)不连通，请输出\(-1\)。
Sample Input 1
4 2 3
1 2 2
2 3 3
1 2
1 3
1 4
Sample Output 1
0
2
-1
Sample Input 2
4 4 1
1 2 3
1 3 4
3 4 2
2 4 1
1 2
Sample Output 2
0
Sample Input 3
5 5 1
1 2 48
2 3 49
3 5 50
1 4 10
4 5 100
1 5
Sample Output 3
10
Data Range
对于\(30\%\)的数据，\(N,M,Q \le 100\)。
对于\(60\%\)的数据，\(N,M,Q \le 1000\)。
对于\(100\)的数据，\(N,M,Q \le 10^5\)，\(v \le 1000\)。
Oops! 本题目还没有解答！
助教老师们编题的速度，已经超过了解题的速度！
OJ翻了一新，但本解答集还大多用的是2017-2019级，甚至更早的同学们贡献的答案。
如果你已经AC了，可以的话，请您参考添加页面，与大家一起分享你的题解！