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

速度还可以 250ms

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):
    currentDistance, currentV = heapq.heappop(pq)
    visited[currentV] = 1

    if currentV == n:
        print(currentDistance)
        break
    for v,weight in neighbors[currentV]:
        if visited[v]==0:
            heapq.heappush(pq,(currentDistance+weight,v))

else:
    print(-1)