华为OD机试真题精讲：流浪地球（Python/Java/C++多语言实现）

华为OD机试真题精讲：流浪地球（Python/Java/C++多语言实现）

一、题目描述（2025B卷高频100分题）

在《流浪地球》的背景设定中，地球需要从当前位置（记为节点0）移动到目标星系（记为节点n-1），途中需经过若干行星发动机空间站（节点1~n-2）。各空间站之间存在单向航道连接，每条航道包含两个核心属性：

1. 燃料消耗：通过该航道地球需消耗的核聚变燃料量；
2. 通行成本：通过该航道需消耗的重元素资源点数。

给定n个节点的航道图（邻接表形式）、初始燃料总量F，要求找到从节点0到节点n-1的最小通行成本路径（路径总燃料消耗≤F）；若不存在满足条件的路径，返回-1。

关键约束

• 节点数量：1 ≤ n ≤ 1000；
• 航道数量：1 ≤ m ≤ 5000；
• 单条航道燃料消耗：1 ≤ fuel ≤ 100；
• 初始燃料总量：1 ≤ F ≤ 1000；
• 单条航道通行成本：1 ≤ cost ≤ 100；
• 无自环、无重复航道，所有数值均为正整数；
• 时间限制1秒，空间限制256MB。

示例说明