OpenJudge

E01S02:谁可以走到我

总时间限制:
2000ms
单个测试点时间限制:
1000ms
内存限制:
65536kB
描述

给出一个有向图G(无重边/自环),以及点s,找出所有能走到s的点,以及它们走到s的最短路径。

输入
第一行包含3个整数N、M、s,表示该图共有N个结点和M条无向边,点s序号。(N <= 5000,M <= 500000)
接下来M行,每行包含3个整数{u,v,w},表示有一条长度为w的有向边,u指向v。
输出
若干行,依次输出能走到s的结点标号以及最短路径。
每行包含2个整数,分别为序号和最短路径。
*要求序号从小到大输出。
样例输入
4 3 1
1 2 2
2 1 4
3 1 3
样例输出
2 4
3 3
全局题号
15790
添加于
2017-08-08
提交次数
3
尝试人数
2
通过人数
2