题目信息

题目类型
练习
题目年份
2025
题目题型
编程题
关 键 词
求单源最短路的Bellman-Ford算

题目题干

求单源最短路的Bellman-Ford算法

请编写程序,实现在带负值权的有向图中求单源最短路的 Bellman-Ford 算法。bWc100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

输入格式:

输入首先在第一行给出两个正整数,依次为当前要创建的图的顶点数 n(≤100)和边数 m。bWc100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
随后 m 行,每行给出一条有向边的起点编号、终点编号、权重。顶点编号从 0 开始,权重(在区间 [−100,100] 内)为整数。同行数字均以一个空格分隔。bWc100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

输出格式:

参考样例。首先第一行输出bWc100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

BF returns x

其中 x 为 1 对应算法成功,为 0 对应存在负值圈导致算法不成功的情况。bWc100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
随后按顶点编号的升序,每行输出一个顶点的信息,格式为:bWc100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

dist[i] = x

其中 i 为顶点编号;x 为顶点 0 到顶点 i 的最短距离。即使存在负值圈,也输出算法得到的距离信息。bWc100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

输入样例 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

答案解析

相关题目

求所有点对间最短路的Floyd-Warshall算法请编写程序,实现在带权有向图中求所有点对间最短路的 Floyd-Warshall 算法。 输入格式: 输入首先在第一行给出两个正整数,依次为当前要
求单源最短路的Bellman-Ford算法请编写程序,实现在带负值权的有向图中求单源最短路的 Bellman-Ford 算法。 输入格式: 输入首先在第一行给出两个正整数,依次为当前要创建的图的顶点
求单源最短路的Dijkstra算法请编写程序,实现在带权的有向图中求单源最短路的 Dijkstra 算法。 注意:当多个待收录顶点路径等长时,按编号升序进行收录。 输入格式: 输入首先在第一行给出两
哥尼斯堡的“七桥问题” 哥尼斯堡是位于普累格河上的一座城市,它包含两个岛屿及连接它们的七座桥,如下图所示。 可否走过这样的七座桥,而且每桥只走过一次?瑞士数学家欧拉(Leonhard Euler
哥尼斯堡的“七桥问题” 哥尼斯堡是位于普累格河上的一座城市,它包含两个岛屿及连接它们的七座桥,如下图所示。 可否走过这样的七座桥,而且每桥只走过一次?瑞士数学家欧拉(Leonhard Euler
双连通分量本题请你编写程序,输出给定无向连通图中的割点和割边。 输入格式: 输入首先在第一行给出图中最大顶点数量,即正整数 kMaxVertex(≤20)。 第二行给出两个正整数,依次为当前要创建的
欧拉回路本题请你编写程序,输出给定无向连通图中的欧拉回路。 输入格式: 输入首先在第一行给出图中最大顶点数量,即正整数 kMaxVertex(≤20)。 第二行给出两个正整数,依次为当前要创建的图的
强连通分量本题请你编写程序,输出给定有向图中的各个强连通分量,并统计强连通分量的个数。 输入格式: 输入首先在第一行给出 2 个整数,依次为有向图的顶点数 n(0<n≤15)和边数 m。 随后
验证六度空间理论所谓“六度空间理论”是指:在世界上任何两个陌生人之间所间隔的人数不会超过 6 个。本题就请你编写程序,根据输入的人与人之间的关系,统计以某个人为起点的所有满足该理论(即与该起点之间间隔
图的连通性判断请编写程序,用广度优先搜索输出给定无向图中的各个连通分量,并判断给定的无向图是否连通。 注意输出顺序规定如下: 每个连通分量的输出从其中编号最小的顶点开始; 不同连通分量按其第一个顶点

提示声明

  • 免责声明:本站资源均来自网络或者用户投稿,仅供用于学习和交流:如有侵权联系删除!
  • 温馨提示:本文属于积分文章,需要充值获得积分或升级VIP会员,也可在会员中心投稿获取。

猜你喜欢