解题思路

核心模型

这是一个多约束最短路（MCSP, Multi-Constrained Shortest Path）问题： 在有向图中从 src 到 dst，最小化费用 cost，同时满足：

• 累计能量 energy ≤ C
• 累计时间 time ≤ T
• 经过边数 steps ≤ k+1（中转 ≤ k）

题目内容

在星系联邦的星际物流系统中，你需要规划一条从 起始星球 到 目标星球 的路径。每个虫洞跃迁包含以下约束：

虫洞属性：跃迁费用(信用点)、能量消耗(千兆焦耳)、时间消耗(小时)

飞船限制：最大能量容量 $C$ 千兆焦耳(总能量 $≤C$ )、时间窗口 $T$ 小时(总耗时 $≤T$ )、最多中转 $k$ 次(中转不计起始终端)

特殊规则：每个虫洞只能使用一次(防止时间悖论)

求满足所有约束的最小跃迁费用，不存在可行路径时返回 $-1$ 。

输入描述

• 第一行输入 6 个整数，分别表示： n 星球数量 src 起始星球 dst 目标星球 k 最大中转次数 C 最大能量容量 T 最大允许时间

• 第二行输入整数 m，表示虫洞数量。

• 接下来 m 行，每行 5 个整数：from, to, cost, energy, time，表示一条虫洞。

输出描述

满足所有约束的最小跃迁费用 $(int)$ 。

样例1

3 0 2 1 10 10
3
0 1 5 2 3
1 2 3 1 4
0 2 10 5 5

样例输出

8

说明

路径 $0→1→2$ ：

费用 $5+3=8$

能量 $2+1=3<=10$

时间 $3+4=7<=10$

中转次数 $1≤1$ 直接路径 $0→2$ 费用更高 $(10)$ ，因此最小费用为 $8$ 。