华为 · 图 · 算法编程题
华为 图 n ≤ 100 时限 1 秒 / 256 MB

题目描述

帕秋莉正在红魔馆的地下图书馆构建一套魔导传输网络。该网络由 n 个编号为 0 n-1 的魔导单元组成，单元之间通过 m 条双向传输通道进行信息交换。
每条通道连接两个特定的单元，并具有一定的传输延迟 c 。由于魔导路径的复杂性，同一对单元之间可能存在多条不同的通道。
咲夜需要协助帕秋莉计算特定单元对之间的最小传输总延迟。如果两个单元之间存在多条路径，咲夜必须找出总延迟之和最小的一条；若两个单元之间没有任何路径相连，则认为它们无法建立通信。

输入输出

输入描述
第一行包含两个整数 n, m ( 1 ≤ n ≤ 100, 1 ≤ m ≤ n^2 )，分别表示魔导单元的数量和传输通道的数量。
接下来的 m 行，每行包含三个整数 a, b, c ( 0 ≤ a, b < n, 1 ≤ c ≤ 100 )，表示单元 a 与单元 b 之间存在一条双向传输通道，其延迟为 c 。
接下来的一个整数 k ( 1 ≤ k ≤ 10^4 )，表示咲夜需要进行的查询次数。
接下来的 k 行，每行包含两个整数 i, j ( 0 ≤ i, j < n )，表示询问单元 i 与单元 j 之间的最小传输总延迟。
输出描述
输出共 k 行。对于每组查询，输出一个整数表示最小延迟。若两单元间不存在任何路径，则输出 0 。

样例共 1 组

样例 1 · - 单元 0 与 1 连接（延迟 10），1 与 2 连接（延迟 20）。从 0 到 2 的最短路径为 0 → 1 → 2 ，总延迟为 10 + 20 = 30 。 - 单元 0 与 3 之间没有路径连通，按照要求输出 0。 - 单元 3 与 4 直接通过一条延迟为 40 的通道连接，这是它们之间的唯一路径。
输入
5 3
0 1 10
1 2 20
3 4 40
3
0 2
0 3
3 4
输出
30
0
40

算法解析依据充分

考点：图

数据规模 n ≤ 100 ｜ 限制 1 秒 / 256MB ｜ 标准输入输出

题目画像

  • 数据规模：k ≤ 1e4，n ≤ 100
  • 元素值域：c ≤ 100（注意整数类型选择，避免溢出）
  • 复杂度门槛：允许 O(n³) ~ O(n⁴) 的多重循环，可以放心枚举。
  • 源站时限：1 秒（牛客口径，非本题专属门槛）

解题思路

推荐方向：图

本题切入点

多查询最短路：n≤100 而查询数达 1e4，先跑 Floyd 预处理全源最短路（重边取最小），每次查询 O(1) 输出，不可达按题意输出 0。

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

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

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

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

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

该范式的通法易错点

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

对照本题

  • 数据规模 n ≤ 100，允许 O(n³) ~ O(n⁴) 的多重循环，可以放心枚举。
  • 元素值域最大到 100 —— 求和 / 相乘时记得开 64 位整数。

样例解读

样例 1：输入 5 3 / 0 1 10 / 1 2 20 / 3 4 40 / 3 / 0 2 / 0 3 / 3 4 → 输出 30 / 0 / 40

  • 单元 0 与 1 连接（延迟 10），1 与 2 连接（延迟 20）。从 0 到 2 的最短路径为 0 → 1 → 2 ，总延迟为 10 + 20 = 30 。
  • 单元 0 与 3 之间没有路径连通，按照要求输出 0。
  • 单元 3 与 4 直接通过一条延迟为 40 的通道连接，这是它们之间的唯一路径。

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

本题来源：2026年-华为-04月23号留学生开发岗。

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