2416 - 最短路和负环

题目描述

给出一个有 N 个节点,M 条边的带权有向图。

要求你写一个程序, 判断这个有向图中是否存在负权回路。 如果从一个点沿着某条路径出发, 又回到了自己, 而且所经过的边上的权和小于0, 就说这条路是一个负权回路。如果存在负权回路, 只输出一行-1

如果不存在负权回路, 再求出一个点 S (1≤S≤N)到每个点的最短路的长度。 约定: SS 的距离为 0 , 如果 S 与这个点不连通, 则输出NoPath

输入

第一行:点数 N (2≤N≤1000),边数 M (1≤M≤1000),源点 S (1≤S≤N);

以下 M 行, 每行三个整数 a, b, c 表示点a, b(1≤a, b≤N)之间连有一条边, 权值为 c (-1,000,000≤c≤1,000,000)
请注意:本题两点之间可能存在多条边。

输出

如果存在负权环, 只输出一行-1

如果不存在负环,请按如下要求输出:

N 行, 第 i 行描述 S 点到 i 点的最短路:
如果 Si 不连通, 输出NoPath;
如果 i = S, 输出 0;

其他情况输出 Si 的最短路的长度。

样例

输入

6 8 1
1 3 4
1 2 6
3 4 -7
6 4 2
2 4 5
3 6 3
4 5 1
3 5 4

输出

0
6
4
-3
-2
7
标签
题目参数
时间限制 1 秒
内存限制 512 MB
提交次数 0
通过人数 0
金币数量 1 枚
难度 入门


上一题 下一题