201. 【应-47-2·难】最短路径表
中等
Python
📋 题目描述
给定一张无向无权图（N 个节点 1..N，M 条边）和起点 start。请求出 start 到每个节点 i（1<=i<=N）的最短距离 dist[i]：不可达输出 -1，自身输出 0。请用 BFS 实现。
📥 输入描述
第一行三个整数 N M start（1<=N<=10^4, 0<=M<=10^5, 1<=start<=N）。
接下来 M 行，每行两个整数 u v，表示无向边 u-v（u!=v）。
📤 输出描述
一行 N 个整数：dist[1] dist[2] ... dist[N]（空格分隔）。
输入样例
5 4 1 1 2 1 3 2 4 3 5
输出样例
0 1 1 2 2
提示：BFS：dist=[-1]*(N+1)；dist[start]=0；q=deque([start])。
while q：u=q.popleft()，遍历 adj[u]，dist[v]==-1 则 dist[v]=dist[u]+1 并入队。
请登录后提交代码