华为 · 图 · 算法编程题
华为 图 N ≤ 1e3 时限 2 秒 / 256 MB

题目描述

小红正在设计一套电动公交路径规划系统。城市中有 N 个路口和 M 条单向道路，每条道路有通行时间和耗电量。公交车从起点 S 出发，要到达终点 T。
公交车初始电量为 E，最大电量为 maxE。只有当当前剩余电量不少于某条道路的耗电量时，才能通过这条道路。
城市中有 K 个充电站。公交车到达充电站后，可以选择花费 1 单位时间将电量充满，也可以不充电。不能在非充电站充电，也不能在道路中途充电。
请计算从 S 到 T 的最小总耗时；如果无法到达，输出 -1。

输入输出

输入描述
第一行输入： N K M S T E maxE
- N ：交叉路口数量（ 2 ≤ N ≤ 1000 ，整数）
- K ：充电站数量（ 0 ≤ K ≤ N ，整数）
- M ：单向道路数量（ 1 ≤ M ≤ 1000 ，整数）
- S ：起点路口编号
- T ：终点路口编号
- E ：初始电量（ 0 ≤ E ≤ maxE ）
- maxE ：满电电量（ 1 ≤ maxE ≤ 100 ）
接着是 M 行，每行描述一条道路：
from to time cost
- from, to ：路口编号（ 0 ~ N-1 ），代表该道路从 " from " 路口 到 " to " 路口
- time ：通行时间（正整数）
- cost ：该路段能耗（正整数， ≤ maxE ）
最后一行有 K 个值，每个数代表一个充电站所在路口的编号： CP1 CP2 ... CPK
输出描述
1. 返回公交车从起点 S 到终点 T 的最小总耗时。
2. 若无法到达终点，返回 -1 。

样例共 1 组

样例 1
输入
5 2 6 0 4 3 3
0 1 2 1
0 2 5 2
1 3 3 1
2 3 1 3
3 4 1 2
1 4 2 3
2 3
输出
7

算法解析依据充分

考点：图

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

题目画像

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

解题思路

推荐方向：图

本题切入点

状态扩展最短路：状态为 (路口, 剩余电量)，边权为时间；充电站可花 1 时间充满，用 Dijkstra 求解，电量不足的边不可通行，不可达输出 −1。

把关系抽象成点与边，再按问的类型选遍历/最短路/连通性算法。

思路框架（图 通法 · 非本题专属）

  1. 建图：邻接表（稀疏）或邻接矩阵（稠密）。
  2. 问「最少几步 / 最短路径」且边权为 1 → BFS。
  3. 问「是否连通 / 需要加几条边连通」→ 并查集 / 连通块计数。
  4. 问「带权最短路」→ Dijkstra（非负权）或 Floyd（点数小、多源）。
  5. 问「依赖顺序」→ 拓扑排序。

实现要点：注意是有向图还是无向图，无向图加边记得双向。

复杂度：时间 O(V+E) 遍历 / O(E log V) Dijkstra ｜ 空间 O(V+E)

该范式的通法易错点

  • 无向图只加了单向边。
  • BFS 入队时没标记访问，导致重复入队。

对照本题

  • 数据规模 N ≤ 1e3，允许 O(n²)；若 n ≤ 300，O(n³) 通常也跑得动，需看具体常数。
  • 元素值域最大到 100 —— 求和 / 相乘时记得开 64 位整数。

样例

样例 1

  • 输入：5 2 6 0 4 3 3 / 0 1 2 1 / 0 2 5 2 / 1 3 3 1 / 2 3 1 3 / 3 4 1 2 / 1 4 2 3 / 2 3
  • 输出：7

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

本题来源：2026年-华为-05月13号开发岗。

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