问题1732--最短路板题

1732: 最短路板题

时间限制: 1 Sec  内存限制: 128 MB
提交: 96  解决: 51
[提交] [状态] [讨论版] [命题人:]

题目描述

如题，给出一个有向图，请输出从某一点出发到所有点的最短路径长度。有重边和自环，非负权。

输入

第一行包含三个整数n m  s分别表示点的个数、有向边的个数、出发点的编号。
接下来m行每行包含三个整数u,v,w表示一条u到v的，长度为w的边。

输出

输出一行n个整数，第i个表示s到第i个点的最短路径，若不能到达则输出−1。

样例输入

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

提示

对于 20%的数据：1≤n≤5，1≤m≤15；
对于 40%的数据：1≤n≤100，1≤m≤10000；
对于 100%的数据：1≤n≤1000，1≤m≤100000；

来源/分类

最短路 

[提交] [状态]