#433. 地道
地道
No testdata at current.
题目描述
外星人又双叒叕攻打土拨鼠星球了,土拨鼠们为了防御建立了n个根据地,由m条地道相连,表示每个战士经过第i条边所消耗的士气值,现在指挥部想向每个根据地分别派发一名士兵,请求出这个士兵到达根据地后消耗的最少士气值.
也就是给出一个n个点,m个有向边,求从s点出发,到达每个点的最短路.题目保证不会出现负环和自己指向自己的边,但会有边权为负的边,但不保证所有点都能到达!
Format
Input
第一行输入两个数 n,m,s 接下来m行每行输入3个数,分别是这条边的起点终点和消耗的士气.
Output
输出n行每行一个数,第i行表示从s到i所消耗的最少士气值,如果不能到达则输出NO
Samples
5 6 1
2 1 31
3 2 52
3 4 11
4 5 14
1 5 -81
1 3 -10
0
42
-10
1
-81
Limitation
;
;
;
;