OpenJudge

1:[模版]单源最短路dijkstra-邻接表

总时间限制:
2000ms
内存限制:
140000kB
描述

给出一个有向图,请输出从某一点出发到所有点的最短路径长度。


输入
第一行包含三个整数N、M、S,分别表示点的个数、有向边的个数、出发点的编号。
N<=10000,M<=500000;空间限制为128MB
接下来M行每行包含三个整数ui、vi、wi,分别表示第i条有向边的出发点、目标点和长度。
输出
一行,包含N个用空格分隔的整数,其中第i个整数表示从点S出发到点i的最短路径长度(若S=i则最短路径长度为0,若从点S无法到达点i,则最短路径长度为2147483647)
样例输入
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
提示
*注意:用邻接矩阵存图会MLE
来源
https://www.luogu.org/problem/show?pid=3371#sub
全局题号
14868
添加于
2017-05-05
提交次数
41
尝试人数
17
通过人数
17