3146 问题 E: 蓝桥杯2023年第十四届省赛真题-网络稳定性

时间限制: 1.5s 内存限制: 256MB 提交: 1989 解决: 252
题目描述
有一个局域网,由 n 个设备和 m 条物理连接组成,第 i 条连接的稳定性为wi
对于从设备 A 到设备 B 的一条经过了若干个物理连接的路径,我们记这条路径的稳定性为其经过所有连接中稳定性最低的那个。
我们记设备 A 到设备 B 之间通信的稳定性为 A 至 B 的所有可行路径的稳定性中最高的那一条。
给定局域网中的设备的物理连接情况,求出若干组设备 xi 和 yi 之间的通信稳定性。如果两台设备之间不存在任何路径,请输出 −1 。
输入
输入的第一行包含三个整数 n, m, q ,分别表示设备数、物理连接数和询问数。
接下来 m 行,每行包含三个整数 ui , vi ,wi ,分别表示 ui 和 vi 之间有一条稳定性为 wi 的物理连接。
接下来 q 行,每行包含两个整数 xi , yi ,表示查询 xi 和 yi 之间的通信稳定性。
输出
输出 q 行,每行包含一个整数依次表示每个询问的答案。
样例输入
5 4 3
1 2 5
2 3 6
3 4 1
1 4 3
1 5
2 4
1 3
样例输出
-1
3
5
提示
对于 30% 的评测用例,n, q ≤ 500,m ≤ 1000 ;
对于 60% 的评测用例,n, q ≤ 5000,m ≤ 10000 ;
对于所有评测用例,2 ≤ n, q ≤ 105,1 ≤ m ≤ 3 × 105,1 ≤ ui , vi , xi , yi ≤ n,
1 ≤ wi ≤ 106,u≠ vi,xi yi

比赛公告

尽可能可能会加不加班GVv看吧过于高抗压液体肥人多热水的无色特色台湾色娃娃