2026 华为OD机试真题9月2日华为OD上机新系统考试真题 100 分题型

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

题目描述

某电力公司使用无人机对 n 个电力塔进行巡检。每个电力塔 i 位于坐标 (xi,yi)，无人机从基地（坐标 (0,0)）出发，需要依次飞达每个电力塔完成巡检后结束任务，无需返回基地。

无人机同一时刻只能飞向一个电力塔，请规划巡检顺序，使无人机飞行的总距离最短（两个坐标点间按曼哈顿距离计算，即 ∣x1−x2∣+∣y1−y2∣），输出最短总距离。

2026 华为OD机试真题9月2日华为OD上机新系统考试真题 100 分题型

输入描述

• n：电力塔数量，1≤n≤15
• xi,yi：第 i 个电力塔的坐标，0≤xi,yi≤200

输出描述

输出最短总距离（整数）

示例1

输入

3
[[1,2],[3,1],[2,3]]

输出

8

说明

3 个电力塔：A(1,2)、B(3,1)、C(2,3)。基地为 O(0,0)。

• 巡检顺序 A→C→B：O→A 距离 ∣1−0∣+∣2−0∣=3，A→C 距离 ∣1−2∣+∣2−3∣=2，C→B 距离 ∣2−3∣+∣3−1∣=3。总距离 3+2+3=8
• 巡检顺序 A→B→C：O→A 距离 3，A→B 距离 ∣1−3∣+∣2−1∣=3，B→C 距离 ∣3−2∣+∣1−3∣=3。总距离 9
• 巡检顺序 B→A→C：O→B 距离 4，B→A 距离 3，A→C 距离 2。总距离 9

其余顺序总距离均不小于 8，最短总距离为 8。

示例2

输入

2
[[1,1],[2,2]]

输出

4

说明

2 个电力塔：A(1,1)、B(2,2)。基地为 O(0,0)。

• 巡检顺序 A→B：O→A 距离 ∣0−1∣+∣0−1∣=2，A→B 距离 ∣1−2∣+∣1−2∣=2。总距离 2+2=4
• 巡检顺序 B→A：O→B 距离 ∣0−2∣+∣0−2∣=4，B→A 距离 ∣2−1∣+∣2−1∣=2。总距离 4+2=6

最短总距离为 4。

解题思路

核心思想

这题本质上是一个小规模旅行商问题，但起点固定在基地 (0,0)，且巡检结束后不需要回基地。

因为 n <= 15，可以用状态压缩动态规划。dp[mask][i] 表示已经访问过的塔集合为 mask，并且最后停在塔 i 时的最短总距离。起点距离则是从基地直接飞到第一座塔的曼哈顿距离。

算法步骤

1. 预处理任意两座塔之间的曼哈顿距离。
2. 初始化所有单点状态：基地到第 i 座塔的距离。
3. 枚举访问集合 mask，再枚举当前停留塔 i。
4. 尝试把未访问的塔 j 接到后面，更新 dp[mask | (1<<j)][j]。
5. 最终答案是访问完全部塔后，停在任意塔的最小值。

复杂度分析

设塔数为 n。

• 时间复杂度：O(2^n * n^2)
• 空间复杂度：`O(2^n *