#4057. 1382. 最短路(Spfa)

    ID: 4057 传统题 1000ms 128MiB 尝试: 0 已通过: 0 难度: 5 上传者: 标签>一本通在线评测图论最短路数据结构

1382. 最短路(Spfa)

题目描述

给定 MM 条边, NN 个点的带权无向图。求 11 到 NN 的最短路。

输入格式

第一行两个整数N、M(1≤N≤100000,0≤M≤500000)。接下来M行,每行三个正整数a、b、c,表示a、b间一条长为c的无向边;1≤a,b≤N,1≤c≤1000。允许重边和自环,保证1到N可达。

输出格式

一个整数,表示 11 到 NN 的最短距离。

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

提示

【样例解释】

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

来源

一本通在线评测 ybtbas-1382