Dotcpp  >  编程题库  >  蓝桥杯2023年第十四届省赛真题-网络稳定性
题目 3146:

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

时间限制: 3s 内存限制: 320MB 提交: 1924 解决: 231

题目描述

有一个局域网，由 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，ui ≠ vi，xi ≠ yi 。
标签
 
分享 

                
                
                

                                        

                        
                        

                                                            
                                                        
                            
                            
                            
                        

                    

                    

                        
                    

                


                


                


                

                  上一题
                  下一题
                


            

            


                    

                        

                            
通过率

                        

                                                
                       
                    

                                        

                        

                            
统　计

                        

                        

                    

                    

                        

                            
解题报告

                        

                                                
                    


                    

                        

                            
推荐题目

                        

                        

                            

                            
蓝桥杯2024年第十五届决赛真题-兔子集结
蓝桥杯2024年第十五届省赛真题-好数
蓝桥杯2024年第十五届省赛真题-R 格式
蓝桥杯2024年第十五届决赛真题-旋转九宫格
蓝桥杯2024年第十五届决赛真题-最长子段