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

from os import error
from math import inf
import heapq
n,m=map(int,input().split(" "))
dic=dict()
for i in range(1,m+1):
    u,v,w=map(int,input().split(" "))
    if u not in dic.keys():
        dic[u]=dict()
    if v not in dic.keys():
        dic[v]=dict()
    dic[u][v]=w
    dic[v][u]=w
distance=dict()
for key in dic.keys():
    distance[key]=float('inf')
distance[1]=0
vist=[]
pq=[]
heapq.heappush(pq,(0,1))
while pq:
    d,node=heapq.heappop(pq)
    if node in vist:
        continue
    vist+=[node]
    for neibor,weight in dic[node].items():
        if d+weight<distance[neibor]:
            distance[neibor]=d+weight
            heapq.heappush(pq,(distance[neibor],neibor))
try:
    print(distance[n])
except KeyError as e:
    print(-1)