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

from collections import defaultdict
import heapq
n, m = map(int, input().split())
G = defaultdict(set)
for i in range(m):
    u, v = map(int, input().split())
    G[u].add((v, 1)) #w = 1
    G[v].add((u, 1)) # w = 1
# print(G)
distances = {v: float("inf") for v in G}
# print(distances)
start = 1
distances[start] = 0
heap = [(0, start)]
heapq.heapify(heap)
while heap:
    distance, node = heapq.heappop(heap)
    # print(node)
    if distance > distances[node]:
        continue
    for neighbor, weight in G[node]:
        alt = distance + weight
        if distances[neighbor] > alt:
            distances[neighbor] = alt
            heapq.heappush(heap, (alt, neighbor))
# print(distances)
t = distances[n] if n in distances else -1
print( -1 if t is float("inf") else t )