路径

题目描述

小蓝学习了最短路径之后特别高兴，他定义了一个特别的图，希望找到图中的最短路径。
小蓝的图由2021个结点组成，依次编号1至2021。
对于两个不同的结点a, b，如果a和b的差的绝对值大于21，则两个结点之间没有边相连；
如果a和b的差的绝对值小于等于21，则两个点之间有一条长度为a 和b 的最小公倍数的无向边相连。

例如：

• 结点1 和结点23 之间没有边相连；结点3 和结点24 之间有一条无向边，长度为24；

• 结点15 和结点25 之间有一条无向边，长度为75。

请计算，结点1 和结点2021 之间的最短路径长度是多少。
提示：建议使用计算机编程解决问题。

本题考点

1. $a$与$b$的最小公倍数：$\frac{a \times b}{gcd(a,b)}$
2. 最短路问题：spfa，Dijkstra朴素或优化

答案：10266837

Code

import heapq


N = 2025
M = 100 * N
inf = float("inf")
graph = [-1] * N
dist = [inf] * N
state = [0] * N
w = [0] * M
e = [0] * M
ne = [0] * M
idx = 0

def when_to_add(a,b):
    if abs(a-b) <= 21:
        c = a * b / gcd(a,b)
        add(a,b,c)
        add(b,a,c)
        return True
    else:
        return False


def gcd(a,b):
    if b:
        return gcd(b,a % b)
    return a


def add(a,b,c):
    global idx
    e[idx] = b
    ne[idx] = graph[a]
    graph[a] = idx
    w[idx] = c
    idx += 1


def Dijkstra():
    heap = []
    dist[1] = 0
    heapq.heappush(heap,(0,1))

    while heap:
        distance,node = heapq.heappop(heap)
        if state[node]:
            continue
        else:
            state[node] = 1

        cur = graph[node]
        while cur != -1:
            j = e[cur]
            if dist[j] > distance + w[cur]:
                dist[j] = distance + w[cur]
                heapq.heappush(heap,(dist[j],j))
            cur = ne[cur]

    if dist[n] == inf:
        return -1
    else:
        return int(dist[n])


if __name__ == "__main__":
    n = int(input())
    m = 0
    for i in range(1,n+1):
        for j in range(i+1,n+1):
            if when_to_add(i,j):
                m += 1

    print(Dijkstra())