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

import sys
from collections import defaultdict
import heapq

n, m = list(map(int,input().strip().split(' ')))

adjacent_mat = defaultdict(list)

min_dis = [5001] * (n+1) 
not_processed = set()

for i in range(m):
    u, v = list(map(int,input().strip().split(' ')))
    adjacent_mat[u].append(v)
    adjacent_mat[v].append(u)

processed = set()
pq = [] # 记录当前所有从起始点到点i还未确定最短路径的距离以及点i

heapq.heappush(pq,(0,1)) # 起始点为1，距离为0

while len(pq):
    cur_dis, cur_pos = heapq.heappop(pq)
    processed.add(cur_pos)

    if cur_pos == n:
        print(cur_dis)
        break
    
    for v in adjacent_mat[cur_pos]:
        if v in processed: continue
        heapq.heappush(pq,(cur_dis+1,v))
else:
    print(-1)