路径

本题为填空题，只需要算出结果后，在代码中使用输出语句将所 填结果输出即可

小蓝学习了最短路径之后特别高兴，他定义了一个特别的图，希 望找到图中的最短路径。

小蓝的图由2021个结点组成，依次编号1至2021。

对于两个不同的结点ab，如果a和b的差的绝对值大于21，则两个结点之间没有边相连;如果a和b的差的绝对值小于等于21，则两个点之间有一条长度为a和b的最小公倍数的无向边相连。

例如: 结点1和结点23 之间没有边相连;结点3 和结点24 之间有一条无向边，长度为24;结点15 和结点25之间有一条无向边，长度为 75。

请计算，结点1和结点2021之间的最短路径长度是多少

提示:建议使用计算机编程解决问题

MyCode

Dijkstra最短路径算法的python函数实现 | Ianwusb's Blog

def lcm(a,b):
    x,y=a,b
    while y:
        x,y=y,x%y
    return int((a*b)/x)
def dijkstra(graph,starting_node,node_num):#graph[u][v]表示边e=(u,v)的权值，不存在时设为inf
    # 起始节点starting_node,节点数量node_num
    used = [False for _ in range(node_num)]  # 标记数组，used[v]值为False说明该顶点还没有访问过，在S中，否则在U中！
    distance = [float('inf') for _ in range(node_num)]  # 距离数组，distance[i]表示从原点s到i的最短距离，distance[s]=0
    #cost = [[float('inf') for _ in range(node_num)] for _ in range(node_num)]  # cost[u][v]表示边e=(u,v)的权值，不存在时设为inf
    distance[starting_node]=0
    while True:
        v=-1#v在这里相当于是一个哨兵，对包含起点s做统一处理！
        for u in range(node_num):#从未使用过的顶点中选择一个距离最小的顶点
            if not used[u] and (v==-1 or distance[u]<distance[v]):
                v=u
        if v==-1:#说明所有顶点都维护到S中了！
            break
        used[v]=True#将选定的顶点加入到S中，同时进行距离更新
        for u in range(node_num):#更新U中各个顶点到起点s的距离.之所以更新U中顶点的距离，是因为上一步中确定了k是求出的最短路径节点
            distance[u]=min(distance[u],distance[v]+graph[v][u])

    return distance

#建图....begin
cost = [[0 for _ in range(2021)] for _ in range(2021)]
for i in range(2021):
    for j in range(2021):
        if (abs((i+1)-(j+1))<=21):
            w=lcm(i+1,j+1)
            cost[i][j]=w
        elif (abs((i+1)-(j+1))>21):
            cost[i][j]=float('inf')
        if (i==j):
            cost[i][j] = 0
#建图....end
print(dijkstra(cost,0,2021))