学习导图：
【模板】单源最短路径
亲，题目链接请戳这里
题目描述
给定一个n个点，m条有向边的带非负权图，请你计算从s出发，到每个点的距离。
数据保证你能从s出发到任意点。
输入格式
第一行为三个正整数n, m,s。第二行起m行，每行三个非负整数uL;, u;, u;，表示从u;到v;有一条权值为w;的有向边。
输出格式
输出一行n个空格分隔的非负整数，表示s到每个点的距离。
参考题解
import heapq from collections import defaultdict # 核心代码 def dirjkstra(): # 各节点到start的最短距离 dirs = [float('inf')] * (n + 1) dirs[start] = 0 # 已用节点，比set还快20% 所有没有释放False seen = [False] * (n + 1) pq = [] heapq.heappush(pq, (0, start)) # BFS while pq: # 获取 _, u = heapq.heappop(pq) # 该节点是否用过 if seen[u]: continue else: seen[u] = True # 找到邻接节点 nodeList = graph[u] for v, w in nodeList: t = dirs[u] + w if t < dirs[v]: dirs[v] = t # 如果该邻接节点没有访问过才把该最短边加进去 if not seen[v]: heapq.heappush(pq, (t, v)) if dirs[-1] == float('inf'): return -1 else: return dirs[-1] # 输入 n, m = map(int, input().split()) # 初始化 start = 1 # 建图 graph = defaultdict(list) for _ in range(m): u, v, w = map(int, input().split()) graph[u].append((v,w)) answer = dirjkstra() print(answer)
【蓝桥真题】单源最短路径
试题：路径
本体总分：10分
【问题描述】
小蓝学习了最短路径之后特别高兴，他定义了一个特别的图，希望找到图中的最短路径。
小蓝的图由 2021个结点组成，依次编号1至2021。
对于两个不同的结点a, b，如果a和b的差的绝对值大于21，则两个结点之间没有边相连;如果a和b的差的绝对值小于等于21，则两个点之间有一条长度为a和 b的最小公倍数的无向边相连。
例如:结点1和结点23之间没有边相连;结点3和结点24之间有一条无向边，长度为24;结点15和结点25之间有一条无向边，长度为75。
请计算，结点1和结点2021之间惘最短路径长度是多少？
提示:建议使用计算机编程解决问题。
参考题解：（答案：10266837）
import heapq from collections import defaultdict def gcd(a, b): if a < b: a, b = b, a if a % b == 0: return b else : return gcd(b, a%b) def lcm(a, b): return int(a * b / gcd(a, b))
