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

此题中任意两点之间距离是 1，可以直接用广度优先搜索（BFS), 第一次到达n 号点的时候就是最短距离。

from collections import deque
from collections import defaultdict
def main():
    n,m=map(int, input().split()) #有个小坑：点数是 5000，n表示目的点的序号，并不表示说点的序号就是0到n-1
    edges=defaultdict(list)
    for i in range(m):
        u,v=map(int,input().split())
        edges[u].append(v)
        edges[v].append(u)
    visited=set()
    q=deque()#用一个队列就来进行bfs
    q.append((0,1))#将1号加入队列
    while q: #insight: 这道题中提到两个点之间距离是1，所以只需要用bfs,第一次到达n所需要的距离就是最短距离
        d,u=q.popleft()
        visited.add(u)
        for v in edges[u]:
             if v==n:
                return d+1
             if v not in visited:
                q.append((d+1,v))
    return -1
print(main())