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

import sys
import heapq
n, m = map(int, input().split())
edg = [[] for i in range(5100)]
vis = [0 for i in range(5100)]
for i in range(m):
    u, v, w = map(int, input().split())
    edg[v].append((u, w))
    edg[u].append((v, w))
    

h = []
heapq.heappush(h, (0, 1))
while h:
    t = heapq.heappop(h)
    d, v = t[0], t[1]
    if vis[v]:
        continue
    vis[v] = 1
    if vis[n] == 1:
        print(d)
        break
    for e in edg[v]:
        nxt, w = e[0], e[1]
        if vis[nxt]: continue
        heapq.heappush(h, (w + d, nxt))
if vis[n] == 0:
    print(-1)

优先队列(堆里面只需要记录节点编号，不需要记录边，一个贪心算法