阿良的python算法之路（dirjkstra单源最短路径）

阿良的python算法之路（dirjkstra单源最短路径）

目录

【模板】单源最短路径

参考题解

【蓝桥真题】单源最短路径

参考题解：

---

【模板】单源最短路径

亲，题目链接请戳这里

参考题解

import heapq

# 输入
n, m, start = map(int, input().split())

# 初始化
inf = 2 ** 31 - 1
MAX_SIZE = n + 10

# 建图
graph = {x: [] for x in range(1, n + 1)}
for _ in range(m):
    u, v, w = map(int, input().split())
    graph[u].append((v,w))

# 核心代码
def dirjkstra():
    # 各节点到start的最短距离
    dirs = [inf] * MAX_SIZE
    dirs[start] = 0

    # 已用节点，比set还快20%
    seen = [False] * MAX_SIZE

    pq = []
    heapq.heappush(pq, (0, start))

    # BFS
    while pq:
        # 获取
        _, now_node = heapq.heappop(pq)
        
        # 该节点是否用过
        if seen[now_node]:
            continue
        else:
            seen[now_node] = True

        # 找到邻接节点
        nodeList = graph[now_node]
        for sub_node, sub_dist in nodeList:
            t = dirs[now_node] + sub_dist
            if t < dirs[sub_node]:
                dirs[sub_node] = t
                # 如果该邻接节点没有访问过才把该最短边加进去
                if not seen[sub_node]:
                    heapq.heappush(pq, (t, sub_node))
                
    return dirs

answer = dirjkstra()

print(" ".join(map(str, answer[1:n+1])))

【蓝桥真题】单源最短路径

参考题解：（答案：10266837）

import heapq

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))

n = 2021
inf = 2 ** 31 - 1
MAX_SIZE = n + 10

def init_graph():
    graph = {x: [] for x in range(1, n + 1)}
    for i in range(1, 2022):
        for j in range(1, 2022):
            if abs(i-j) <= 21:
                if i == j :
                    continue
                else:
                    graph[i].append([j, lcm(i, j)])

    return graph


graph = init_graph()
def dirjkstra(start):
    dirs = [inf] * MAX_SIZE
    dirs[start] = 0

    seen = [False] * MAX_SIZE

    pq = []
    heapq.heappush(pq, (0, start))

    while pq:
        _, now_node = heapq.heappop(pq)
        
        if seen[now_node]:
            continue
        else:
            seen[now_node] = True

        edgeList = graph[now_node]
        for sub_node, sub_dist in edgeList:
            t = dirs[now_node] + sub_dist
            if t < dirs[sub_node]:
                dirs[sub_node] = t

                if not seen[sub_node]:
                    heapq.heappush(pq, (t, sub_node))
                    
    return dirs

dirs = dirjkstra(1)
print(dirs[2021])
# 10266837