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

from collections import defaultdict
import heapq

def dijkstra(e, s):
    """
    输入：
    e:邻接表
    s:起点
    返回：
    dis:从s到每个顶点的最短路长度
    """
    dis = defaultdict(lambda: float("inf"))
    dis[s] = 0
    q = [(0, s)]
    vis = set()
    while q:
        _, u = heapq.heappop(q)
        if u in vis:
            continue
        vis.add(u)
        for v, w in e[u]:
            if dis[v] > dis[u] + w:
                dis[v] = dis[u] + w
                heapq.heappush(q, (dis[v], v))
    return dis


s = 1
# n个结点，m条边
n,m = map(int, input().split())
# 构建邻接表，其元素为{u：[（v1，w1），(v2,w2)]}
neighbors = defaultdict(list)
for _ in range(m):
    u,v = map(int, input().split())
    w = 1
    neighbors[u].append((v,w))
    neighbors[v].append((u,w))
    
dis = dijkstra(neighbors, s)[n]
print((lambda x: -1 if x == float('inf') else x)(dis))