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

找了半天没有看到python的代码
这个题也好奇怪，我开始并没有设置固定的节点数为5000，就会一直有案例过不去，可能是有什么边界条件？怎么改都改不对，设置了个5000瞬间好了
from collections import defaultdict, deque

def bfs(n, target, edge):
    # 构建邻接表时，添加节点范围的检查
    d = defaultdict(list)
    for u, v in edge:
        d[u].append(v)
        d[v].append(u)

    q = deque([1])
    dis = [-1] * (n + 1)
    tag = [False]*(n+1)
    dis[1] = 0
    tag[1] = True

    while q:
        node = q.popleft()
        for neighbor in d[node]:
            if not tag[neighbor]:
                tag[neighbor] = True
                dis[neighbor] = dis[node] + 1
                q.append(neighbor)

    return dis[target]

# 输入处理
n, m = map(int, input().split())
edge = [tuple(map(int, input().split())) for _ in range(m)]

# 调用函数并输出结果
print(bfs(5000, n, edge))