Skip to content

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了,可以的话,请您参考添加页面,与大家一起分享你的题解!