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

dijkstra，权重为1的简单情况

from collections import defaultdict
import heapq
def SSP(edges,start_node,end_node):
    g=defaultdict(list)
    for u,v in edges:
        g[u].append((1,v))
        g[v].append((1,u))

    if end_node not in g:
        return -1

    distances={k:float('inf') for k in g}
    visited=set()
    pq=[(0,start_node)]

    while pq:
        cur_dis,cur_node=heapq.heappop(pq)
        if cur_node in visited:
            continue
        visited.add(cur_node)
        for w,v in g[cur_node]:
            dis=cur_dis+w
            if dis<distances[v]:
                distances[v]=dis
                heapq.heappush(pq,(dis,v))
        if cur_node == end_node:
            break
    return distances[end_node] if distances[end_node]<float('inf') else -1

n,m=map(int,input().split(' '))
e=[]
for _ in range(m):
    e.append(map(int,input().split(' ')))
print(SSP(e,1,n))