题解 | 【模板】单源最短路2

from collections import defaultdict
import sys
import heapq
input=sys.stdin.readline
n,m = map(int, input().split())
neighbors = defaultdict(list)
for _ in range(m):
    u,v,w = map(int, input().split())
    neighbors[u].append((v,w))
    neighbors[v].append((u,w))

pq = []
heapq.heappush(pq,(0,1)) #tuple[0]是优先级，在这里用距离表示，tuple[1]是顶点编号。
visited = [0]*5001
while len(pq):
    cur_d, cur_v = heapq.heappop(pq) # 优先队列弹出距离最小的那个
    visited[cur_v] = 1 # 标记访问过
    if cur_v == n: 
        print(cur_d)
        break
    for v, w in neighbors[cur_v]:# 访问当前cur_v 的近邻和权值
        if visited[v] == 0:
            heapq.heappush(pq, (cur_d+w, v)) #自动排序
else:
    print(-1)