华为OD机试真题精讲：流浪地球（Python/Java/C++多语言实现）
华为OD机试真题精讲：流浪地球（Python/Java/C++多语言实现）
一、题目描述（2025B卷高频100分题）
在《流浪地球》的背景设定中，地球需要从当前位置（记为节点0）移动到目标星系（记为节点n-1），途中需经过若干行星发动机空间站（节点1~n-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。
示例说明
| 输入格式（逐行输入） |
|---|