无权图最短路径-模板题


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

There are no comments at the moment.