← 返回题目
题库练习 单源最短路径2
← 上一题 下一题 →

A635 | 单源最短路径2

时间限制1s
内存限制128MB
通过 / 提交0/0

题目描述

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

输入格式

第一行包含三个整数 $n,m,s$，分别表示点的个数、有向边的个数、出发点的编号。

接下来 m 行每行包含三个整数 $u,v,w$，表示一条 $u$->$v$ 的，长度为 $w$ 的边。

输出格式

若存在负环输出 no solution，否则输出一行 $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
输入 #2
3 3 1
1 2 5
2 3 6
3 1 -15
输出 #2
no solution
C++ 编辑器
输入
输出