#Pybt34210. 最短路(Spfa)

    ID: 1054 传统题 1000ms 256MiB 尝试: 1 已通过: 0 难度: 普及+/提高- 上传者: 标签>最短路径赛制:OI来源:wyfoj http://127.0.0.1

最短路(Spfa)

最短路(Spfa)

题目描述

给定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

提示

【样例解释】

注意图中可能有重边和自环,数据保证11到NN有路径相连。