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

import sys, heapq
# import heapq

def mini_path(n,m,adj):

    D = [float('inf')]*(5000+1)
    # print(D)
    D[1] = 0
    heap =[]
    heapq.heappush(heap,(0,1))

    while heap:
        # pop minimum element determined by 1st entry
        current_D, u = heapq.heappop(heap) 
        if u == n:
            return current_D
        if current_D > D[u]:
            continue
        for v in adj[u]:
            if current_D+1 < D[v]:
                D[v]=current_D+1
                heapq.heappush(heap, (D[v],v))
           

    return -1

a = sys.stdin.read().split()
n,m = int(a[0]), int(a[1])

idx = 2
edge = []
adj = [[] for _ in range(5000+1)]
for _ in range(m):
    u,v = int(a[idx]), int(a[idx+1])

    adj[u].append((v))
    adj[v].append((u))
    idx += 2

path = mini_path(n,m,adj)
print(path)