Logo Quest Online Judge

QOJ

时间限制:1 s 空间限制:512 MB

#1087. 「一本通 3.3 练习 3」Easy SSSP

统计

题目描述

原题来自:Vijos P1053

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

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

输入格式

第一行三个正整数,分别为点数 $N$,边数 $M$,源点 $S$;

以下 $M$ 行,每行三个整数 $a, b, c$,表示点 $a, b$ 之间连有一条边,权值为 $c$。

输出格式

如果存在负权环,只输出一行 $-1$,否则按以下格式输出:

共 $N$ 行,第 $i$ 行描述 $S$ 点到点 $i$ 的最短路: - 如果 $S$ 与 $i$ 不连通,输出 NoPath; - 如果 $i = S$,输出 $0$。 - 其他情况输出 $S$ 到 $i$ 的最短路的长度。

样例

样例输入

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

数据范围与提示

对于全部数据,$2\le N\le 1000,1\le M\le 10^5,1\le a,b,S\le N,|c|\le 10^6$。