3906: 最短路径SPFA

内存限制：128 MB 时间限制：1.000 S
评测方式：文本比较 命题人：
提交：6 解决：3

题目描述

在图论中，寻找两点之间的最短路径是一个经典问题。然而，当图中的边权值允许为负数时，传统的 Dijkstra 算法将不再适用。此外，如果图中存在一个总权值为负的环路（负权环），那么沿着该环路无限循环可以使路径的总权值无限减小，此时最短路径将不存在。现在，你需要编写一个程序，给定一个包含 
n 个节点和 m 条有向边的带权图，以及一个指定的源点 s 。请计算从源点 s 

输入

输入的第一行包含三个整数 n 、 m 和 s ，分别表示图中的节点总数、有向边的总数以及源点编号
接下来的 m 行，每行包含三个整数 a 、 b 和 c ，表示存在一条从节点 a 指向节点 b 的有向边，该边的权值为 c 

输出

如果图中存在从源点可达的负权环，输出一行字符串：Graph contains negative weight cycle。 如果不存在负权环，第一行输出：Shortest distances from source s:（其中 s 为输入的源点编号）。 第二行输出 n 个值，分别表示从源点到节点 1 到节点 n 的最短距离。如果某个节点不可达，则输出 INF，否则输出对应的最短距离数值，数值之间用空格隔开，行末换行

样例输入 复制 

4 5 2
3 1 6
3 2 1
2 1 1
2 4 5
1 4 3

样例输出 复制 

Shortest distances from source 2:
1 0 INF 4

来源/分类

提交提交记录统计露一手!