无权图最短路径-模板题
Submit solution
Points:
100
Time limit:
1.0s
Memory limit:
4M
Author:
Problem type
Allowed languages
C, C++
📘 题目名称:最短社交距离
📝 题目描述:
在某社交平台上,有 n 位用户,编号为 0 到 n-1。 他们之间有 m 对好友关系,每对好友关系是双向的(即无向边)。你可以认为这些用户形成了一张无权图。
平台管理员想知道:从用户 0 开始,最少需要通过几次好友推荐才能将消息传递给每一个用户?
请你计算从用户 0 出发,到所有其他用户的最短距离(即最少经过多少个好友才能到达)。
如果某个用户无法通过任何路径与 0 相连,则输出 -1。
📥 输入格式:
第一行输入两个整数 n m,分别表示用户数量和好友关系数量。 接下来 m 行,每行两个整数 u v,表示用户 u 和用户 v 是好友(无向边)。
📤 输出格式:
输出一行 n 个整数,第 i 个整数表示从用户 0 到用户 i 的最短路径长度(经过的边数),若无法到达,则输出 -1。
📌 数据范围:
- 1 <= n <= 1000
- 0 <= m <= n*(n-1)/2
- 0 <= u, v < n
- u != v,无重边
🔍 示例输入:
6 5
0 1
0 2
1 3
3 4
4 5
✅ 示例输出:
0 1 1 2 3 4
✅ 解释:
从用户 0 出发:
- 到自己距离为 0
- 到 1 和 2 只需一跳
- 到 3 需要走 0→1→3,两跳
- 到 4 需要 3 跳,5 需要 4 跳
Comments