2026 华为OD机试真题 7月15日华为OD上机新系统考试真题 200 分题型

点击查看华为 OD 机试真题完整目录：2026最新华为OD机试新系统卷 + 双机位C卷 真题题库目录｜全覆盖题库 + 逐点算法考点详解

题目描述

四年校园时光即将结束，小明和室友计划一次难忘的毕业旅行。他们准备从 A 城市出发，前往他们已经久仰的 B 城市。两座城市之间有多种出行方案，既可直达，也可途经其他城市中转，每条路线的费用不相同。

请帮助他们在预算 w 内，找到花费最少的路线。

2026 华为OD机试真题 7月15日华为OD上机新系统考试真题 200 分题型

点击查看华为 OD 机试真题完整目录：2026最新华为OD机试新系统卷 + 双机位C卷 真题题库目录｜全覆盖题库 + 逐点算法考点详解

输入描述

前有三个整数 n,m,w：

• n：城市数量（2≤n≤100）
• m：路线数量（1≤m≤1000）
• w：最大预算（1≤w≤105）

接下来是一个二维数组，记录了所有的路线信息。每条路线有 3 个整数 u,v,cost：

• u：起点城市（1≤u≤n）
• v：终点城市（1≤v≤n）
• cost：所需费用（1≤cost≤105）

输出描述

• 若存在满足预算的最优路线，返回最小花费；
• 若不存在，则返回 -1。

补充说明

1. 出发城市编号为 1，目的地城市编号为 n 所代表的值。
2. 每条路线的起点和终点都不相同（u != v），且只能单方向通行（u→v，不能 v→u）。
3. 从城市 u 到城市 v，不存在多条不同费用的路线。

示例1

输入

3,3,10,[[1,2,5],[2,3,5],[1,3,8]]

输出

8

说明

解释：从城市 1 到城市 3，直达花费 8。在预算内最优。

中转途经城市 2： 5+5=10，费用更高。

示例2

输入

4,4,20,[[1,2,5],[2,3,5],[3,4,5],[1,4,25]]

输出

15

说明

解释：直达 25 超出预算。

路径： 1→2→3→4 花费 15。

为最小可行方案。

示例3

输入

3,3,5,[[1,2,3],[2,3,3],[1,3,10]]

输出

-1

说明

解释：所有可行路径都超过预算 5，返回 -1 表示无解。

解题思路

核心思想

所有路线费用均为正数，要求从城市 1 到城市 n 的最小花费，因此可以把城市看作有向图节点、路线看作有向正权边，使用 Dijkstra 算法求单源最短路。

求出最短花费后，再与预算 w 比较：如果最短花费不超过预算，输出该费用；如果目的城市不可达，或最短花费超过预算，则输出 -1。

算法步骤

1. 解析输入中的 n、m、w 和 m 条道路。
2. 建立有向邻接表，u -> v 的边权为 cost。
3. 初始化距离数组，dist[1]=0，其他城市为无穷大。
4. 使用小根堆维护当前待扩展的最小花费城市。
5. 每次取出当前花费最小的城市，尝试用它更新相邻城市的最短距离。
6. Dijkstra 结束后检查 dist[n]，若不超过预算输出最短花费，否则输出 -1。

复杂度分析

设城市数为 n，路线数为 m。

时间复杂度：O((n + m) log n)，每条边最多触发一次有效松弛，堆操作为对数级。

空间复杂度：O(n + m)，主要用于邻接表、距离数组和优