#274. 单源最短路径(标准版)
单源最短路径(标准版)
题目描述:
2018 年 7 月 19 日,某位同学在 [NOI Day 1 T1 归程] 一题里非常熟练地使用了一个广为人知的算法求最短路。
然后呢?
;
;
最终,他因此没能与理想的大学达成契约。
小 F 衷心祝愿大家不再重蹈覆辙。
给定一个 个点, 条有向边的带非负权图,请你计算从 出发,到每个点的距离。
数据保证你能从 出发到任意点。
输入格式:
第一行为三个正整数 。 第二行起 行,每行三个非负整数 ,表示从 到 有一条权值为 的有向边。
输出格式:
输出一行 个空格分隔的非负整数,表示 到每个点的距离。
样例:
4 6 1
1 2 2
2 3 2
2 4 1
1 3 5
3 4 3
1 4 4
0 2 4 3
提示
;
;
;
;
,
。
本题数据可能会持续更新,但不会重测,望周知。