2021省赛 D. 路径
摘要
Title: 2021省赛 D. 路径
Tag: spfa、lcm
Memory Limit: 64 MB
Time Limit: 1000 ms
Powered by:NEFU AB-IN
2021省赛 D. 路径
-
题意
小蓝学习了最短路径之后特别高兴，他定义了一个特别的图，希望找到图 中的最短路径。
小蓝的图由 2021 个结点组成，依次编号 1 至 2021。
对于两个不同的结点 a, b，如果 a 和 b 的差的绝对值大于 21，则两个结点 之间没有边相连；如果 a 和 b 的差的绝对值小于等于 21，则两个点之间有一条 长度为 a 和 b 的最小公倍数的无向边相连。
例如：结点 1 和结点 23 之间没有边相连；结点 3 和结点 24 之间有一条无 向边，长度为 24；结点 15 和结点 25 之间有一条无向边，长度为 75。
请计算，结点 1 和结点 2021 之间的最短路径长度是多少。 -
思路
spfa直接求即可
-
代码
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
40
41
42
43
44
45
46
47
48
49'''
Author: NEFU AB-IN
Date: 2022-03-15 21:18:12
FilePath: \ACM\LanQiao\2021D.py
LastEditTime: 2022-03-15 21:29:32
'''
from collections import deque
N = 2030
INF = int(2e9)
st = [0] * N
dist = [INF] * N
g = [[] for _ in range(N)]
def gcd(a, b):
return gcd(b, a % b) if b else a
def spfa():
q = deque()
q.appendleft(1)
st[1] = 1
dist[1] = 0
while q:
u = q.pop()
st[u] = 0
for v, w in g[u]:
if dist[v] > dist[u] + w:
dist[v] = dist[u] + w
if st[v] == 0:
q.appendleft(v)
st[v] = 1
if dist[2021] > INF / 2:
return -1
return dist[2021]
for i in range(1, 2022):
for j in range(i + 1, 2022):
if abs(i - j) <= 21:
w = i // gcd(i, j) * j
g[i].append([j, w])
g[j].append([i, w])
else:
break
print(spfa())