#4057. 1382. 最短路(Spfa)
1382. 最短路(Spfa)
题目描述
给定 条边, 个点的带权无向图。求 到 的最短路。
输入格式
第一行两个整数N、M(1≤N≤100000,0≤M≤500000)。接下来M行,每行三个正整数a、b、c,表示a、b间一条长为c的无向边;1≤a,b≤N,1≤c≤1000。允许重边和自环,保证1到N可达。输出格式
一个整数,表示 到 的最短距离。
4 4
1 2 1
2 3 1
3 4 1
2 4 12
提示
【样例解释】
注意图中可能有重边和自环,数据保证 到 有路径相连。
来源
一本通在线评测 ybtbas-1382