单源最短路

题目内容

题目描述

给出一个无向图,包含n个顶点(n<=2000),和m条边(m<=100000),图中顶点编号为1到n,边权值均为不超过1000的正整数,求编号为1的点到其他点的最短路长度

输入描述

输入的第一行为两个正整数,代表题目描述中的n,m

接下来m行,每行3个正整数x,y,z,表示图中存在一条x和y之间,权值为z的边

输出描述

输出一行,每行n个正整数,每个正整数后跟一个空格,第i个正整数代表顶点1到顶点i+1的最短路长度,如果不存在最短路则输出-1

样例输入

3 3 1 2 1 2 3 1 1 3 4

样例输出

1 2

提示

提交评测
请登录后再操作

题目描述

单源最短路
1594
0
08Level8
40
25
63%
证书查询 x
请输入证书编号:

请输入正确的证书编号

学员姓名:孙兴民

课程:Scratch Level 1

发证日期:2019.08.15

证书查询

该证书不存在