华为 · 广度优先搜索(BFS) · 算法编程题
华为 广度优先搜索(BFS) N ≤ 1e3 时限 3 秒 / 256 MB

题目描述

在一座未来城市中，一个高度自动化的无人机物流网络负责着全城的包裹配送。
这个网络由 n 个配送站 S_1, S_2, ..., S_n 组成。
无人机可以在这些配送站之间沿着预设的空中走廊进行飞行。
每条空中走廊连接两个配送站，并且是双向通行的。
由于距离、风阻等因素，无人机飞过每条走廊都需要消耗一定的能量，记为 E_uv 。
这个能耗是固定的，且双向飞行的能耗相同 ( E_uv = E_vu )。
当一个配送任务下达时，系统需要从起始站 S_start 规划出一条到达目的站 S_end 的、总能耗最低的飞行路径。
无人机的导航系统遵循最短路径原则。对于一个从 S_start 到 S_end 的任务，系统会计算出一条或多条总能耗最低的路径。
无人机从起始站出发的第一站被称为下一跳。由于可能存在多条能耗并列最低的路径，因此下一跳也可能不止一个。
您的任务是：给定整个物流网络的布局和各条走廊的能耗，并指定起始站和目的站，计算出：
1. 完成该配送任务所需的最低总能耗。
2. 无人机从起始站出发的所有可能的下一跳站点的集合。

输入输出

输入描述
第一行包含两个整数 N 和 K ，分别代表配送站的总数和空中走廊的数量。
1 ≤ N ≤ 1000
1 < K ≤ (N × (N-1)/2)
接下来的 K 行描述了空中走廊的信息。每行包含三个正整数 u, v, e ，分别代表这条走廊连接的两个配送站的编号 S_u, S_v 和飞行所需的能耗 E_uv 。
1 ≤ E_uv ≤ 100
站点编号 u, v 的范围在 [1, N] 内。
最后一行包含两个正整数 S_start 和 S_end ，代表任务的起始站和目的站。
输出描述
输出共两行：
第一行为一个整数，表示从 S_start 到 S_end 的最低总能耗。
第二行为一个或多个正整数，代表所有可能的下一跳站点的编号。请将这些编号按升序排列，并用单个空格分隔。
特殊情况：
1. 如果目的站 S_end 无法从起始站 S_start 到达，则最低能耗输出 `-1`，下一跳集合也输出 `-1`。
2. 如果起始站与目的站相同 ( S_start = S_end )，则最低能耗为 `0`，下一跳集合输出 `-1`。

样例共 1 组

样例 1
输入
19 71
7 9 98
9 14 98
6 11 27
2 10 8
6 8 2
10 11 68
16 17 34
2 13 29
13 18 70
5 7 46
1 5 76
5 12 96
5 17 18
11 16 91
3 18 45
8 10 76
7 13 20
2 9 21
8 12 96
7 10 37
6 16 45
15 19 32
4 11 15
2 6 46
7 11 32
6 13 38
9 18 44
8 14 42
18 19 80
4 7 75
6 9 51
9 12 64
10 13 26
1 13 10
10 15 69
10 19 69
2 19 16
11 12 24
17 19 15
13 17 48
13 16 84
3 11 31
1 9 10
15 16 49
3 8 69
7 8 31
4 15 96
5 8 45
9 10 12
9 16 78
10 17 20
5 18 5
8 17 39
5 6 48
4 16 40
14 16 15
13 15 65
10 16 43
12 18 74
1 14 83
1 10 18
2 5 55
12 16 41
4 18 13
5 16 59
9 13 14
4 8 2
4 12 45
14 18 97
12 17 17
4 13 40
16 18
输出
53
4

算法解析依据一般

考点：广度优先搜索(BFS)

数据规模 N ≤ 1e3 ｜ 限制 3 秒 / 256MB ｜ 标准输入输出

题目画像

  • 数据规模：N ≤ 1e3
  • 元素值域：E_uv ≤ 100（注意整数类型选择，避免溢出）
  • 复杂度门槛：允许 O(n²)；若 n ≤ 300，O(n³) 通常也跑得动，需看具体常数。
  • 源站时限：3 秒（牛客口径，非本题专属门槛）

解题思路

参考方向：广度优先搜索(BFS)

按层扩散搜索，无权图上第一次到达即最短路。

思路框架（广度优先搜索(BFS) 通法 · 非本题专属）

  1. 起点入队并标记已访问。
  2. 每次取队首，把它的所有未访问邻居入队并记录步数。
  3. 第一次访问到目标时，步数即为最少步数。
  4. 网格类题目通常有 4（或 8）个方向，用方向数组统一处理。

实现要点：标记访问必须在入队时做，不能在出队时做，否则会重复入队甚至超时。

复杂度：时间 O(V+E) ｜ 空间 O(V)

该范式的通法易错点

  • 出队才标记访问导致 MLE/TLE。
  • 网格边界没判，越界访问。

对照本题

  • 数据规模 N ≤ 1e3，允许 O(n²)；若 n ≤ 300，O(n³) 通常也跑得动，需看具体常数。
  • 元素值域最大到 100 —— 求和 / 相乘时记得开 64 位整数。
本题在源数据中没有官方考点标签，方向由题面特征推断，仅供参考。

样例

样例 1

  • 输入：19 71 / 7 9 98 / 9 14 98 / 6 11 27 / 2 10 8 / 6 8 2 / 10 11 68 / 16 17 34 / 2 13 29 / 13 18 70 / 5 7 46 / 1 5 76 / 5 12 96 / 5 17 18 / 11 16
  • 输出：53 / 4

解析由校招宝本地引擎整理（依据源站考点标签 / 人工判题标注 / 题面规模信号），非官方题解，仅供思路参考。

本题来源：2025年秋招-华为-10月15号开发岗。

‹ 上一题 全部编程题 下一题 ›
编程算法题为只读内容：无需作答，直接看题与解析 · 本站不提供在线判题 · 解析由校招宝本地引擎整理，非官方题解