2023年蓝桥杯第十四届国赛真题_问题E

提交: 2450 解决: 334

题目描述

有一个局域网，由 n 个设备和 m 条物理连接组成，第 i 条连接的稳定性为w_i。

对于从设备 A 到设备 B 的一条经过了若干个物理连接的路径，我们记这条路径的稳定性为其经过所有连接中稳定性最低的那个。

我们记设备 A 到设备 B 之间通信的稳定性为 A 至 B 的所有可行路径的稳定性中最高的那一条。

给定局域网中的设备的物理连接情况，求出若干组设备 x_i 和 y_i 之间的通信稳定性。如果两台设备之间不存在任何路径，请输出 −1 。

输入

输入的第一行包含三个整数 n, m, q ，分别表示设备数、物理连接数和询问数。

接下来 m 行，每行包含三个整数 u_i , v_i,w_i ，分别表示 u_i 和 v_i 之间有一条稳定性为 w_i 的物理连接。

接下来 q 行，每行包含两个整数 x_i , y_i，表示查询 x_i 和 y_i 之间的通信稳定性。

输出

输出 q 行，每行包含一个整数依次表示每个询问的答案。

样例输入

样例输出

-1
3
5

提示

对于 30% 的评测用例，n, q ≤ 500，m ≤ 1000 ；

对于 60% 的评测用例，n, q ≤ 5000，m ≤ 10000 ；

对于所有评测用例，2 ≤ n, q ≤ 10⁵，1 ≤ m ≤ 3 × 10⁵，1 ≤ u_i , v_i , x_i , y_i ≤ n，

1 ≤ w_i≤ 10⁶，u_i≠ v_i，x_i ≠ y_i 。

请各位参赛选手认真做题，积极备战国赛，争取国一，为学校学院争光添彩，加油！