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

最短路(Spfa)

时间限制: 3s 内存限制: 192MB 提交: 82 解决: 14

题目描述

给定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有路径相连。
标签
  
分享 
































上一题
下一题











通过率












统　计












解题报告











推荐题目








[编程入门]链表之报数问题
[编程入门]链表之节点删除
扫雷游戏地雷数计算
图像模糊处理
你的第一个程序