我是靠谱客的博主 舒适翅膀,这篇文章主要介绍2021年第十二届蓝桥杯 - 省赛 - C/C++大学A组 - D.路径,现在分享给大家,希望可以做个参考。

2021年第十二届蓝桥杯 - 省赛 - C/C++大学A组 - D.路径

在这里插入图片描述

Ideas

算法:最短路径
数据结构:图
思路:根据规则构图,单源最短路径Dijkstra算法。

首先构图其实很简单,就是按照题目的要求来就可以了,这里需要注意的就是最大公约数和最小公倍数的计算函数,其实可以当做模板背下来了。

复制代码
1
2
3
4
5
6
7
def gcd(a, b): return a if b == 0 else gcd(b, a % b) def lcm(a, b): return a * b / gcd(a, b)

然后构造图的时候选择通过邻接矩阵的形式去构建。

复制代码
1
2
3
4
5
graph = [[0] * 2021 for _ in range(2021)] for row in range(2021): for col in range(2021): graph[row][col] = float("inf") if abs(row - col) > 21 else lcm(row + 1, col + 1)

之后就是Dijkstra算法了,简单介绍一下。


Dijkstra单源最短路径算法

松弛操作:对于一对顶点要求最短路径,可以通过中转点将路径变短。

在这里插入图片描述

对于i、j两个节点,如果想让路径变短,只能通过第三个节点k来中转。举个例子,从 1->5 距离为10,但 1->2->5 距离变成9了。

单源最短路径问题指的是从一个点出发,求该点到其它所有顶点的最短路径,也就是说,只能计算起点只有一个的情况。

对于图G=<V, E>上带权的单源最短路径问题,Dijkstra算法设置一个集合S用来记录已经求得最短路径的顶点。

初始时把起点v0放入S中,集合S每并入一个新顶点vi,都要修改原点v0到集合V-S中顶点的当前最短路径长度值。

在这里插入图片描述
从起点到一个顶点的最短路径一定会经过至少一个“中转点”(我们认为起点也是一个“中转点”),如果我们想要求出起点到一个顶点的最短路径,那我们必须要先求出从起点到中转点的最短路径。

对于图G=<V, E>,将所有的点分为两类,一类是已经确定最短路径的点,称为“红点”,另一类是未确定最短路径的点,称为“白点”。

Dijkstra算法的思想:首先将起点的距离标记为0,而后进行n此循环,每次找出一个到起点距离最短的点,将它从白点变为红点,随后枚举所有的白点,如果以此红点为中转到达某个白点的路径更短的话,那么就更新。


通过Dijkstra最短路径算法可以求得结点1到其它所有结点的最短路径,最后直接输出结点1和节点2021之间的最短路径长度就OK啦。

Code

Python

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
import heapq def gcd(a, b): return a if b == 0 else gcd(b, a % b) def lcm(a, b): return a * b / gcd(a, b) def Dijkstra(g, node): n, queue, visit = len(g), list(), set() heapq.heappush(queue, (0, node)) distance = [float("inf") for _ in range(n)] distance[node] = 0 while queue: dist, vertex = heapq.heappop(queue) visit.add(vertex) for i in range(n): val = g[vertex][i] if val != float("inf") and val not in visit and dist + val < distance[i]: distance[i] = dist + val heapq.heappush(queue, (dist + val, i)) return distance if __name__ == '__main__': graph = [[0] * 2021 for _ in range(2021)] for row in range(2021): for col in range(2021): graph[row][col] = float("inf") if abs(row - col) > 21 else lcm(row + 1, col + 1) dis = Dijkstra(graph, 0) print(int(dis[2021 - 1]))

Answer:10266837

最后

以上就是舒适翅膀最近收集整理的关于2021年第十二届蓝桥杯 - 省赛 - C/C++大学A组 - D.路径的全部内容,更多相关2021年第十二届蓝桥杯内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
点赞(68)

评论列表共有 0 条评论

立即
投稿
返回
顶部