蓝桥杯真题省赛2021|蓝桥杯 2021省赛 python 路径算法|动态规划|蓝桥杯

本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。
小蓝学习了最短路径之后特别高兴，他定义了一个特别的图，希望找到图中的最短路径。
小蓝的图由 2021 个结点组成，依次编号 1 至 2021。
对于两个不同的结点 a, b，如果 a 和 b 的差的绝对值大于 21，则两个结点之间没有边相连；如果 a 和 b 的差的绝对值小于等于 21，则两个点之间有一条长度为 a 和 b 的最小公倍数的无向边相连。
例如：结点 1 和结点 23 之间没有边相连；结点 3 和结点 24 之间有一条无向边，长度为 24；结点 15 和结点 25 之间有一条无向边，长度为 75。
请计算，结点 1 和结点 2021 之间的最短路径长度是多少。
提示：建议使用计算机编程解决问题

填空题第四题因为是无向图，所以用Floyd算法
跑的非常慢，要等很长时间
1.计算两点无向边的长度，求两数的最小公倍数（lcm)
2.建立邻接表
3.用Floyd算法：g[i][j]=min(g[i][k]+g[k][j],g[i][j])

from math import * def lcm(a,b): return a*b/gcd(a,b) n=2021 g=[[0 for i in range(1,n+2)] for j in range(1,n+2)] for i in range(1,n+1): for j in range(1,n+1): if i==j: g[i][j]=g[j][i]=0 if abs(i-j)<=21: g[i][j]=g[j][i]=lcm(i,j) else: g[i][j]=g[j][i]=float("inf") for k in range(1,n+1): for i in range(1,n+1): for j in range(1,n+1): if g[i][j]>g[i][k]+g[k][j]: g[i][j]=g[j][i]=g[i][k]+g[k][j] print(dp[1][n])

总结：1.求最小公倍数 2.最短路：Floyd算法（适合n<300的小图）（无向图）（多源最短路径）
2.Dijkstra算法（用bfs,优先队列）

from math import * from queue import * vis=[0 for i in range(2022)] edge=[[] for i in range(2022)] def lcm(a,b): return a*b//gcd(a,b) d=[float('inf') for i in range(2022)] for i in range(1,2022): for j in range(1,2022): if 0dist+w: d[v]=dist+w q.put((d[v],v)) dijkstra() print(d[2021])

3.SPFA算法（问路法）

from math import * from queue import * vis=[0 for i in range(2022)] edge=[[] for i in range(2022)] def lcm(a,b): return a*b//gcd(a,b) d=[float('inf') for i in range(2022)] for i in range(1,2022): for j in range(1,2022): if 0d[p]+w: d[v]=d[p]+w if vis[v]==0: q.put(v) vis[v]=1 spfa() print(d[2021])

Dijkstra算法与Spfa算法的主要区别是：
1. Dijkstra算法用的是优先队列，先弹出距离起点最近的点，并且弹出的时候打标记，打过标记的说明这已经是这个点的最短距离了，再弹出的这个点的距离不是最短距离，也就不用更新相邻点的距离了。（优先队列既存点，也存距离，距离在前面）
2.Spfa算法用到的是队列，问路法，在它距离更新后，进入队列，打上标记，如果他的距离再次跟新，但是它已经在队列里啦（打上标记了），他就不用再进入队列了。(队列只存点）
3.spfa算法可以处理边权为负数的数据，Dijkstra算法不能。
4.spfa不稳定，这道题的话Dijkstra算法是最快的。
【蓝桥杯真题省赛2021|蓝桥杯 2021省赛 python 路径】