#P3732. Network

Network

题目描述

给定一张带权、连通的无向图。对每个询问 (A,B)(A,B),考虑所有从 AA 到 BB 的路径。求这些路径各自的最大边权中的最小值。

输入格式

第一行三个整数 N,M,KN,M,K,依次为顶点数、边数和询问数。顶点编号为 11 至 NN。

接下来 MM 行,每行三个整数 X,Y,DX,Y,D,表示顶点 XX 和 YY 之间有一条权为 DD 的无向边。

接下来 KK 行,每行两个整数 A,BA,B,表示一条询问。本站评测保证 1≤A,B≤N1\le A,B\le N 且 A≠BA\ne B。

输出格式

对每条询问输出一行一个整数。

6 6 8
1 2 5
2 3 4
3 4 3
1 4 8
2 5 7
4 6 2
1 2
1 3
1 4
2 3
2 4
5 1
6 2
6 1
5
5
5
4
4
7
4
5

数据范围

2≤N≤150002\le N\le15000,1≤M≤300001\le M\le30000,1≤K≤200001\le K\le20000,1≤D≤1091\le D\le10^9。

[原赛 Heatwave 解题报告](file://soluton.pdf)