Dotcpp  >  编程题库  >  信息学奥赛一本通T1680-Easy SSSP
题目 3282:

信息学奥赛一本通T1680-Easy SSSP

时间限制: 2s 内存限制: 128MB 提交: 7 解决: 3

题目描述

原题来自: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≤N≤1000,1≤M≤105,1≤a,b,S≤N,∣c∣≤106

标签