Dotcpp  >  编程题库  >  最短路(Spfa)
题目 3110:

最短路(Spfa)

时间限制: 2s 内存限制: 192MB 提交: 102 解决: 20

题目描述

给定M条边， N个点的带权无向图。求1到N的最短路。

输入格式

第一行：N,M(N<=100000，M<=500000)；
接下来M行3个正整数：ai,bi,ci表示ai,bi之间有一条长度为ci的路，ci<=1000。

输出格式

一个整数，表示1到N的最短距离。

样例输入

4 4
1 2 1
2 3 1
3 4 1
2 4 1

样例输出

2

提示

【样例解释】
注意图中可能有重边和自环,数据保证1到N有路径相连。
标签
  
分享 

                
                
                

                                        

                        
                        

                                                            
                                                        
                            
                            
                            
                        

                    

                    

                        
                    

                


                


                


                

                  上一题
                  下一题
                


            

            


                    

                        

                            
通过率

                        

                                                
                       
                    

                                        

                        

                            
统　计

                        

                        

                    

                    

                        

                            
解题报告

                        

                                                
                    


                    

                        

                            
推荐题目

                        

                        

                            

                            
扫雷游戏地雷数计算
图像模糊处理
矩阵剪刀石头布
最好的草
肿瘤面积