Dotcpp  /  编程题库  /  [传智杯]传送门
题目 2320:

[传智杯]传送门

 时间限制: 2s 内存限制: 128MB

题目描述

传智专修学院里有 n 栋教学楼，有 m 条双向通行道路连接这些教学楼，不存在重边和自环。每条道路都有一定的长度，而且所有教学楼之间都可以直接或者间接的通过道路到达。我们可以很容易的求出这些教学楼之间的最短路。

为了使交通更为顺畅，校方决定在两个教学楼里增设一对传送门。传送门可以将这对教学楼的距离直接缩短为 0。利用传送门，某些教学楼之间的最短路的距离就变短了。

由于预算有限，学校里只能安装一对传送门。但是校长希望尽可能方便学生，使任意两点之间的最短路长度的总和最小。当然啦，从 x 教学楼到 y 教学楼的长度和从 y 教学楼到 x 教学楼的长度只需要统计一次就可以了。

输入格式

输入第 1 行两个正整数 n,m(n<=100,m<=1/2*n*(n-1)，代表教学楼和道路数量。

接下来 m 行，每行三个正整数 Xi,Yi,Wi，表示在教学楼Xi 和 Yi 之间，有一条长度为 Wi 的道路。

输出格式

输出一行，在最优方案下的任意点对的最短道路之和。

样例输入

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

样例输出

14

提示

样例如图。当在 1 和 4 号教学楼架设一对传送门时，1 → 2 的最短路是 3，1 → 3 的最短路是 0+2，1 → 4 的最短路是 0，2 → 3 的最短路是 4，2 → 4 的最短路是 3+0，3 → 4 的最短路是 2，最短路之和是 14，是最佳方案。
标签
 
分享 

                
                
                

                                        

                        
                        

                                                            
                                                        
                            
                            
                            
                        

                    

                    

                        
                    

                


                


                


                

                  上一题
                  下一题
                


            

            


                    

                        

                            
通过率

                        

                                                
                       
                    

                                        

                        

                            
统　计

                        

                        

                    

                    

                        

                            
解题报告

                        

                                                
                    


                    

                        

                            
推荐题目

                        

                        

                            

                            
七月树的水题 
[传智杯]软件工程实习
[传智杯]游园会盖章
[传智杯]程序员节发橙子
[传智杯]众数出现的次数