请编写程序,实现在带负值权的有向图中求单源最短路的 Bellman-Ford 算法。
输入格式:
输入首先在第一行给出两个正整数,依次为当前要创建的图的顶点数 n(≤100)和边数 m。
随后 m 行,每行给出一条有向边的起点编号、终点编号、权重。顶点编号从 0 开始,权重(在区间 [−100,100] 内)为整数。同行数字均以一个空格分隔。
输出格式:
参考样例。首先第一行输出
BF returns x
其中 x
为 1 对应算法成功,为 0 对应存在负值圈导致算法不成功的情况。
随后按顶点编号的升序,每行输出一个顶点的信息,格式为:
dist[i] = x
其中 i
为顶点编号;x
为顶点 0 到顶点 i
的最短距离。即使存在负值圈,也输出算法得到的距离信息。
输入样例 1:
5 10
0 1 6
0 3 7
1 2 5
2 1 -2
1 3 8
1 4 -4
3 2 -3
3 4 9
4 2 7
4 0 2
输出样例 1:
BF returns 1
dist[0] = 0
dist[1] = 2
dist[2] = 4
dist[3] = 7
dist[4] = -2
输入样例 2:
7 12
0 1 2
0 3 1
1 4 -10
2 0 4
2 5 5
3 2 2
3 5 8
3 6 4
4 3 2
3 1 3
4 6 6
6 5 1
输出样例 2:
BF returns 0
dist[0] = -5
dist[1] = -13
dist[2] = -14
dist[3] = -16
dist[4] = -18
dist[5] = -11
dist[6] = -12