2026华为OD机试真题 11.1 新系统 - 山区救援路线规划

/* MD / 富文本中的 .toc（含博客园搬家等嵌套结构）；.toc-box 在侧栏，不受影响 */
#content_views .toc,
/* 编辑器常在目录前后插入空 p（:empty 仍占 20px），一并去掉避免顶空隙 */
#content_views.markdown_views > p:empty:has(+ .toc),
#content_views.markdown_views > .toc + p:empty,
/* 富文本旧版目录标记 */
#content_views.htmledit_views #main-toc,
#content_views.htmledit_views #hr-toc,
#content_views.htmledit_views p[id*=\”-toc\”] {
display: none !important;
}
/* 目录去掉后，紧跟的首个标题不再多出一块上边距 */
#content_views.markdown_views > .toc + h1,
#content_views.markdown_views > .toc + h2,
#content_views.markdown_views > .toc + h3,
#content_views.markdown_views > .toc + h4,
#content_views.markdown_views > .toc + p:empty + h1,
#content_views.markdown_views > .toc + p:empty + h2,
#content_views.markdown_views > .toc + p:empty + h3,
#content_views.markdown_views > .toc + p:empty + h4 {
margin-top: 0 !important;
}

山区救援路线规划(Java/Py/C/C++/Js/Go)题解

华为OD机试真题 新系统 华为OD上机考试真题新系统 11月1号 200分题型

华为OD机试新系统真题目录点击查看: 华为OD机试新系统真题题库目录｜机考题库 + 算法考点详解

题目内容

某山区建立了一张应急救援路网，路网中共有n个路口，编号为1～n，每个路口都有各自的海拔高度（米）。救援队从1号路口出发，每到一个路口，只能继续走向它的左路口或右路口，直到走到左右两侧都无路可走的路口(终点）为止，从1号路口走到某个终点的行进路径，称为一条”路线”。

救援队需要权衡两方面因素：

• 每走一段路，如果海拔升高（爬升），这一段的能耗为α×高差；如果海拔降低（下降），这一段的能耗为β×高差，这里的高差取绝对值。一条路线的总能耗为各段能耗之和。
• 海拔极差：一条路线经过的全部路口（包含1号路口）中，最高海拔与最低海拔的差值不能超过安全阀值，否 则气压变化过大，队员有高原反应风险。

你的任务是：在所有海拔极差不超过的路线中，找出总能耗最小的路线。若存在多条能耗相同的路线，选择路口编号序列字典序较小的那条：按顺序逐个比较两条序列的元素，第一个不同的位置上元素更小者更小：若一条序列是另一条序列的前缀，则较短的序列更小。

路网保证以1号路口为根的二叉树

输入描述

n: 路口数量(3 <= n <= 1000)

α 和 β：上坡体力消耗权重，下降体力消耗权重。范围为[1,10]

s: 海拔极差阈值(1 <= s <= 4000)

接下来n行每行包含4个整数，分别表示

id value left right

• id:路口编号
• value:海拔高度(0 <= value <= 10^4)
• left: 左路口编号，没有则为-1
• right:右路口编号，没有则为-1

输出描述

返回总能耗最小的路线。若存在多条能耗相同的路线，选择路口编号序列字典序较小的那条。如果没有任何线路满足要求，返回空。

样例1

输入

7
4 2
500
1 1200 2 3
2 1000 4 5
3 1500 6 7
4 1250 -1 -1
5 600 -1 -1
6 1100 -1 -1
7 2000 -1 -1

输出

1 2 4

说明

共有四条线路:1,2,4 1,2,5 1,3,6 1,3,7
1,2,5 和 1,3,7不满足极差分别为600 800
1,2,4极差为250，能耗为1400
1,3,6极差为400，能耗为2000
因此返回1,2,4

样例2

输入

3
2 2
300
1 500 2 3
2 700 -1 -1
3 300 -1 -1

输出

1 2

解题思路

思路：递归回溯 + 剪枝

C++

#include <bits/stdc++.h>
#include <vector>
using namespace std;

using ll = long long;

struct Node {
int value;
int left, right;
};

vector<Node> tree;

ll bestCost = LLONG_MAX;
vector<int> bestPath;
vector<int> path;

// 比较两条路线，选择字典序较小的路线
bool smaller(vector<int>& a, vector<int>& b) {
int len = min(a.size(), b.size());

for (int i = 0; i < len; i++) {
if (a[i] != b[i]) {
return a[i] < b[i];
}
}

return a.size() < b.size();
}

// DFS 搜索所有合法路线
void dfs(int u, int maxH, int minH, ll cost, int a, int b, int s) {
// 更新当前路径的最高和最低海拔
maxH = max(maxH, tree[u].value);
minH = min(minH, tree[u].value);

// 海拔极差超过阈值，直接剪枝
if (maxH – minH > s) {
return;
}

// 当前能耗已经超过最优答案，直接剪枝
if (cost > bestCost) {
return;
}

path.push_back(u);

// 到达叶子节点
if (tree[u].left == –1 && tree[u].right == –1) {
if (cost < bestCost ||
(cost == bestCost && (bestPath.empty() || smaller(path, bestPath)))) {
bestCost = cost;
bestPath = path;
}

path.pop_back();
return;
}

// 计算下一条边的能耗
auto getCost = [&](int v) -> ll {
int diff = tree[v].value – tree[u].value;

if (diff > 0) {
return a * diff;
}

return b * (–diff);
};

// 继续走向左子节点
if (tree[u].left != –1) {
int v = tree[u].left;
dfs(v, maxH, minH, cost + getCost(v), a, b, s);
}

// 继续走向右子节点
if (tree[u].right != –1) {
int v = tree[u].right;
dfs(v, maxH, minH, cost + getCost(v), a, b, s);
}

path.pop_back();
}

vector<int> solve(int n, int a, int b, int s, vector<vector<int>>& node) {
tree.resize(n + 1);

for (int i = 0; i < n; i++) {
int id, value, left, right;
id = node[i][0];
value = node[i][1];
left = node[i][2];
right = node[i][3];
tree[id] = {value, left, right};
}

// 从根节点 1 开始搜索
dfs(1, tree[1].value, tree[1].value, 0, a, b, s);
return bestPath;
}

int main() {
int n,a,b,s;

cin >> n;
cin >> a >> b;
cin >>s;
vector<vector<int>> node(n);

for (int i = 0; i < n; i++) {
int id, value, left, right;
cin >> id >> value >> left >> right;
node[i] = {id, value, left, right};
}

vector<int> ans = solve(n, a, b, s, node);
// 没有合法路线
if (ans.empty()) {
cout << "";
return 0;
}

// 输出最优路线
for (int i = 0; i < ans.size(); i++) {
if (i > 0) cout << " ";
cout << ans[i];
}

return 0;
}

JAVA

import java.util.*;

public class Main {

static class Node {
int value;
int left, right;

Node(int value, int left, int right) {
this.value = value;
this.left = left;
this.right = right;
}
}

static Node[] tree;
static long bestCost = Long.MAX_VALUE;
static List<Integer> bestPath = new ArrayList<>();
static List<Integer> path = new ArrayList<>();

// 比较两条路线，选择字典序较小的路线
static boolean smaller(List<Integer> a, List<Integer> b) {
int len = Math.min(a.size(), b.size());

for (int i = 0; i < len; i++) {
if (!a.get(i).equals(b.get(i))) {
return a.get(i) < b.get(i);
}
}

return a.size() < b.size();
}

// DFS 搜索所有合法路线
static void dfs(int u, int maxH, int minH, long cost, int a, int b, int s) {
// 更新当前路径的最高和最低海拔
maxH = Math.max(maxH, tree[u].value);
minH = Math.min(minH, tree[u].value);

// 海拔极差超过阈值，直接剪枝
if (maxH – minH > s) {
return;
}

// 当前能耗已经超过最优答案，直接剪枝
if (cost > bestCost) {
return;
}

path.add(u);

// 到达叶子节点
if (tree[u].left == –1 && tree[u].right == –1) {
if (cost < bestCost ||
(cost == bestCost && (bestPath.isEmpty() || smaller(path, bestPath)))) {
bestCost = cost;
bestPath = new ArrayList<>(path);
}

path.remove(path.size() – 1);
return;
}

// 计算下一条边的能耗
if (tree[u].left != –1) {
int v = tree[u].left;
int diff = tree[v].value – tree[u].value;
long nextCost = diff > 0 ? (long) a * diff : (long) b * (–diff);

// 继续走向左子节点
dfs(v, maxH, minH, cost + nextCost, a, b, s);
}

if (tree[u].right != –1) {
int v = tree[u].right;
int diff = tree[v].value – tree[u].value;
long nextCost = diff > 0 ? (long) a * diff : (long) b * (–diff);

// 继续走向右子节点
dfs(v, maxH, minH, cost + nextCost, a, b, s);
}

path.remove(path.size() – 1);
}

static List<Integer> solve(int n, int a, int b, int s, int[][] node) {
tree = new Node[n + 1];

bestCost = Long.MAX_VALUE;
bestPath = new ArrayList<>();
path = new ArrayList<>();

for (int i = 0; i < n; i++) {
int id = node[i][0];
int value = node[i][1];
int left = node[i][2];
int right = node[i][3];

tree[id] = new Node(value, left, right);
}

// 从根节点 1 开始搜索
dfs(1, tree[1].value, tree[1].value, 0, a, b, s);

return bestPath;
}

public static void main(String[] args) {
Scanner sc = new Scanner(System.in);

int n = sc.nextInt();
int a = sc.nextInt();
int b = sc.nextInt();
int s = sc.nextInt();

int[][] node = new int[n][4];

for (int i = 0; i < n; i++) {
for (int j = 0; j < 4; j++) {
node[i][j] = sc.nextInt();
}
}

List<Integer> ans = solve(n, a, b, s, node);

// 没有合法路线
if (ans.isEmpty()) {
System.out.println("");
return;
}

// 输出最优路线
StringBuilder sb = new StringBuilder();
for (int i = 0; i < ans.size(); i++) {
if (i > 0) sb.append(" ");
sb.append(ans.get(i));
}

System.out.println(sb);
}
}

Python

import sys

class Node:
def __init__(self, value, left, right):
self.value = value
self.left = left
self.right = right

bestCost = float('inf')
bestPath = []
path = []
tree = []

# 比较两条路线，选择字典序较小的路线
def smaller(a, b):
length = min(len(a), len(b))

for i in range(length):
if a[i] != b[i]:
return a[i] < b[i]

return len(a) < len(b)

# DFS 搜索所有合法路线
def dfs(u, maxH, minH, cost, a, b, s):
global bestCost, bestPath

# 更新当前路径的最高和最低海拔
maxH = max(maxH, tree[u].value)
minH = min(minH, tree[u].value)

# 海拔极差超过阈值，直接剪枝
if maxH – minH > s:
return

# 当前能耗已经超过最优答案，直接剪枝
if cost > bestCost:
return

path.append(u)

# 到达叶子节点
if tree[u].left == –1 and tree[u].right == –1:
if cost < bestCost or (
cost == bestCost and (not bestPath or smaller(path, bestPath))
):
bestCost = cost
bestPath = path[:]

path.pop()
return

# 计算下一条边的能耗
# 继续走向左子节点
if tree[u].left != –1:
v = tree[u].left
diff = tree[v].value – tree[u].value
nextCost = a * diff if diff > 0 else b * (–diff)

dfs(v, maxH, minH, cost + nextCost, a, b, s)

# 继续走向右子节点
if tree[u].right != –1:
v = tree[u].right
diff = tree[v].value – tree[u].value
nextCost = a * diff if diff > 0 else b * (–diff)

dfs(v, maxH, minH, cost + nextCost, a, b, s)

path.pop()

def solve(n, a, b, s, node):
global tree, bestCost, bestPath, path

tree = [None] * (n + 1)
bestCost = float('inf')
bestPath = []
path = []

for i in range(n):
id, value, left, right = node[i]
tree[id] = Node(value, left, right)

# 从根节点 1 开始搜索
dfs(1, tree[1].value, tree[1].value, 0, a, b, s)

return bestPath

def main():
data = list(map(int, sys.stdin.buffer.read().split()))

idx = 0
n = data[idx]
idx += 1

a, b = data[idx], data[idx + 1]
idx += 2

s = data[idx]
idx += 1

node = []
for i in range(n):
node.append(data[idx:idx + 4])
idx += 4

ans = solve(n, a, b, s, node)

# 没有合法路线
if not ans:
print("")
return

# 输出最优路线
print(" ".join(map(str, ans)))

if __name__ == "__main__":
main()

JavaScript

const readline = require('readline');

const rl = readline.createInterface({
input: process.stdin,
output: process.stdout
});

let lines = [];

rl.on('line', (line) => {
lines.push(line.trim());
});

rl.on('close', () => {
const data = lines.join(' ').split(/\\s+/).map(Number);

let idx = 0;
const n = data[idx++];
const a = data[idx++];
const b = data[idx++];
const s = data[idx++];

const node = [];

for (let i = 0; i < n; i++) {
node.push(data.slice(idx, idx + 4));
idx += 4;
}

const ans = solve(n, a, b, s, node);

// 没有合法路线
if (ans.length === 0) {
console.log('');
return;
}

// 输出最优路线
console.log(ans.join(' '));
});

// 比较两条路线，选择字典序较小的路线
function smaller(a, b) {
const len = Math.min(a.length, b.length);

for (let i = 0; i < len; i++) {
if (a[i] !== b[i]) {
return a[i] < b[i];
}
}

return a.length < b.length;
}

let tree;
let bestCost;
let bestPath;
let path;

// DFS 搜索所有合法路线
function dfs(u, maxH, minH, cost, a, b, s) {
// 更新当前路径的最高和最低海拔
maxH = Math.max(maxH, tree[u].value);
minH = Math.min(minH, tree[u].value);

// 海拔极差超过阈值，直接剪枝
if (maxH – minH > s) {
return;
}

// 当前能耗已经超过最优答案，直接剪枝
if (cost > bestCost) {
return;
}

path.push(u);

// 到达叶子节点
if (tree[u].left === –1 && tree[u].right === –1) {
if (cost < bestCost ||
(cost === bestCost && (bestPath.length === 0 || smaller(path, bestPath)))) {
bestCost = cost;
bestPath = path.slice();
}

path.pop();
return;
}

// 计算下一条边的能耗
// 继续走向左子节点
if (tree[u].left !== –1) {
const v = tree[u].left;
const diff = tree[v].value – tree[u].value;
const nextCost = diff > 0 ? a * diff : b * (–diff);

dfs(v, maxH, minH, cost + nextCost, a, b, s);
}

// 继续走向右子节点
if (tree[u].right !== –1) {
const v = tree[u].right;
const diff = tree[v].value – tree[u].value;
const nextCost = diff > 0 ? a * diff : b * (–diff);

dfs(v, maxH, minH, cost + nextCost, a, b, s);
}

path.pop();
}

function solve(n, a, b, s, node) {
tree = new Array(n + 1);

bestCost = Infinity;
bestPath = [];
path = [];

for (let i = 0; i < n; i++) {
const [id, value, left, right] = node[i];
tree[id] = { value, left, right };
}

// 从根节点 1 开始搜索
dfs(1, tree[1].value, tree[1].value, 0, a, b, s);

return bestPath;
}

Go

package main

import (
"bufio"
"fmt"
"os"
)

type Node struct {
value int
left, right int
}

var tree []Node
var bestCost int64 = 1<<63 – 1
var bestPath []int
var path []int

// 比较两条路线，选择字典序较小的路线
func smaller(a, b []int) bool {
length := len(a)
if len(b) < length {
length = len(b)
}

for i := 0; i < length; i++ {
if a[i] != b[i] {
return a[i] < b[i]
}
}

return len(a) < len(b)
}

// DFS 搜索所有合法路线
func dfs(u, maxH, minH int, cost int64, a, b, s int) {
// 更新当前路径的最高和最低海拔
if tree[u].value > maxH {
maxH = tree[u].value
}
if tree[u].value < minH {
minH = tree[u].value
}

// 海拔极差超过阈值，直接剪枝
if maxH–minH > s {
return
}

// 当前能耗已经超过最优答案，直接剪枝
if cost > bestCost {
return
}

path = append(path, u)

// 到达叶子节点
if tree[u].left == –1 && tree[u].right == –1 {
if cost < bestCost ||
(cost == bestCost && (len(bestPath) == 0 || smaller(path, bestPath))) {
bestCost = cost
bestPath = append([]int(nil), path…)
}

path = path[:len(path)–1]
return
}

// 计算下一条边的能耗
// 继续走向左子节点
if tree[u].left != –1 {
v := tree[u].left
diff := tree[v].value – tree[u].value

var nextCost int64
if diff > 0 {
nextCost = int64(a) * int64(diff)
} else {
nextCost = int64(b) * int64(–diff)
}

dfs(v, maxH, minH, cost+nextCost, a, b, s)
}

// 继续走向右子节点
if tree[u].right != –1 {
v := tree[u].right
diff := tree[v].value – tree[u].value

var nextCost int64
if diff > 0 {
nextCost = int64(a) * int64(diff)
} else {
nextCost = int64(b) * int64(–diff)
}

dfs(v, maxH, minH, cost+nextCost, a, b, s)
}

path = path[:len(path)–1]
}

func solve(n, a, b, s int, node [][]int) []int {
tree = make([]Node, n+1)

bestCost = 1<<63 – 1
bestPath = []int{}
path = []int{}

for i := 0; i < n; i++ {
id := node[i][0]
value := node[i][1]
left := node[i][2]
right := node[i][3]

tree[id] = Node{value, left, right}
}

// 从根节点 1 开始搜索
dfs(1, tree[1].value, tree[1].value, 0, a, b, s)

return bestPath
}

func main() {
in := bufio.NewReader(os.Stdin)
out := bufio.NewWriter(os.Stdout)
defer out.Flush()

var n, a, b, s int
fmt.Fscan(in, &n)
fmt.Fscan(in, &a, &b)
fmt.Fscan(in, &s)

node := make([][]int, n)

for i := 0; i < n; i++ {
node[i] = make([]int, 4)
fmt.Fscan(in, &node[i][0], &node[i][1], &node[i][2], &node[i][3])
}

ans := solve(n, a, b, s, node)

// 没有合法路线
if len(ans) == 0 {
fmt.Fprintln(out)
return
}

// 输出最优路线
for i := 0; i < len(ans); i++ {
if i > 0 {
fmt.Fprint(out, " ")
}
fmt.Fprint(out, ans[i])
}
fmt.Fprintln(out)
}

C语言

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

typedef long long ll;

typedef struct {
int value;
int left, right;
} Node;

Node *tree;
int *bestPath, *path;
int bestLen = 0;
int pathLen = 0;
ll bestCost = LLONG_MAX;

// 比较两条路线，选择字典序较小的路线
int smaller(int a[], int lenA, int b[], int lenB) {
int len = lenA < lenB ? lenA : lenB;

for (int i = 0; i < len; i++) {
if (a[i] != b[i]) {
return a[i] < b[i];
}
}

return lenA < lenB;
}

// DFS 搜索所有合法路线
void dfs(int u, int maxH, int minH, ll cost, int a, int b, int s) {
// 更新当前路径的最高和最低海拔
if (tree[u].value > maxH) {
maxH = tree[u].value;
}
if (tree[u].value < minH) {
minH = tree[u].value;
}

// 海拔极差超过阈值，直接剪枝
if (maxH – minH > s) {
return;
}

// 当前能耗已经超过最优答案，直接剪枝
if (cost > bestCost) {
return;
}

path[pathLen++] = u;

// 到达叶子节点
if (tree[u].left == –1 && tree[u].right == –1) {
if (cost < bestCost ||
(cost == bestCost &&
(bestLen == 0 || smaller(path, pathLen, bestPath, bestLen)))) {
bestCost = cost;
bestLen = pathLen;

for (int i = 0; i < pathLen; i++) {
bestPath[i] = path[i];
}
}

pathLen—;
return;
}

// 计算下一条边的能耗
// 继续走向左子节点
if (tree[u].left != –1) {
int v = tree[u].left;
int diff = tree[v].value – tree[u].value;

ll nextCost;
if (diff > 0) {
nextCost = (ll)a * diff;
} else {
nextCost = (ll)b * (–diff);
}

dfs(v, maxH, minH, cost + nextCost, a, b, s);
}

// 继续走向右子节点
if (tree[u].right != –1) {
int v = tree[u].right;
int diff = tree[v].value – tree[u].value;

ll nextCost;
if (diff > 0) {
nextCost = (ll)a * diff;
} else {
nextCost = (ll)b * (–diff);
}

dfs(v, maxH, minH, cost + nextCost, a, b, s);
}

pathLen—;
}

int main() {
int n, a, b, s;

scanf("%d", &n);
scanf("%d %d", &a, &b);
scanf("%d", &s);

tree = (Node *)malloc((n + 1) * sizeof(Node));
bestPath = (int *)malloc((n + 1) * sizeof(int));
path = (int *)malloc((n + 1) * sizeof(int));

for (int i = 0; i < n; i++) {
int id, value, left, right;
scanf("%d %d %d %d", &id, &value, &left, &right);

tree[id].value = value;
tree[id].left = left;
tree[id].right = right;
}

// 从根节点 1 开始搜索
dfs(1, tree[1].value, tree[1].value, 0, a, b, s);

// 没有合法路线
if (bestLen == 0) {
printf("\\n");
} else {
// 输出最优路线
for (int i = 0; i < bestLen; i++) {
if (i > 0) {
printf(" ");
}
printf("%d", bestPath[i]);
}
printf("\\n");
}

free(tree);
free(bestPath);
free(path);

return 0;
}

​