A653. 单源最短路径1
编程题
普及/提高-
知识点
题目描述
给出一个可能有重边的有向图，请输出从某一点出发到所有点的最短路径长度。
输入格式
第一行包含三个整数 $n,m,s$，分别表示点的个数、有向边的个数、出发点的编号。
接下来 $m$ 行每行包含三个整数 $u,v,w$，表示一条 $u \rightarrow v$的，长度为 $w$ 的边。
接下来 $m$ 行每行包含三个整数 $u,v,w$，表示一条 $u \rightarrow v$的，长度为 $w$ 的边。
输出格式
输出一行 $n$ 个整数，第 $i$ 个表示 $s$ 到第 $i$ 个点的最短路径，若不能到达则输出 $-1$。
输入输出样例
输入 #1
4 6 1 1 2 2 2 3 2 2 4 1 1 3 5 3 4 3 1 4 4
输出 #1
0 2 4 3
说明/提示
$1\le n\le 10^6,1\le m\le 2\times10^6,1\le u,v\le n,1\le w\le 10^9$