2026-10-02：有限电量到达目标节点的最少时间。用go语言，给定一张包含 n 个顶点的带权有向图，顶点编号为 0 到 n-1。图中的边由 edges 表示，每条边 [u, v, t] 表示从顶点 u 指向顶点 v，经过这条边需要耗时 t 秒。另有一个初始电量 power、一个长度为 n 的数组 cost，以及起点 source 和终点 target。cost[u] 表示信号要从顶点 u 沿任意一条出边继续发送时，需要消耗的电量。
信号在第 0 秒从 source 出发，初始电量为 power。到达某个顶点时不会扣电；只有当信号准备离开该顶点、沿某条出边继续前进时，才需要先保证当前剩余电量不少于 cost[u]，然后剩余电量减少 cost[u]。每经过一条边，累计时间增加这条边的耗时。
现在要求计算信号从 source 到 target 的可行路径。优先使到达 target 的总时间最小；如果存在多条路径都能达到这个最小总时间，则选择到达 target 时剩余电量最大的那条路径。返回一个包含两个整数的结果：第一个是最小总时间，第二个是该最小总时间下的最大剩余电量。如果信号无法到达 target，则返回 [-1, -1]。
1 <= n <= 1000。
0 <= edges.length <= 1000。
edges[i] = [ui, vi, ti]。
0 <= ui, vi <= n - 1。
1 <= ti <= 100000。
1 <= power <= 1000。
cost.length == n。
1 <= cost[i] <= 2000。
0 <= source, target <= n - 1。
输入： n = 5, edges = [[0,1,1],[1,4,1],[0,2,1],[2,3,1],[3,4,1]], power = 4, cost = [2,3,1,1,1], source = 0, target = 4。
输出： [3,0]。
解释：
信号从节点 0 出发，拥有 4 个单位的电量。
路径 0 -> 1 -> 4 无效，因为离开节点 0 后，信号剩余 2 个单位的电量，这小于 cost[1] = 3。
有效路径 0 -> 2 -> 3 -> 4 总共花费时间为 3。
沿着这条路径消耗的总电量为 cost[0] + cost[2] + cost[3] = 4，剩余电量为 0。
因此，答案为 [3, 0]。
题目来自力扣3977。
1. 把图整理成邻接表
首先，代码把输入的边数组edges转换成邻接表。
每一条边[u, v, t]表示：
• 从节点
u出发；• 可以到达节点
v；• 经过这条边需要花费
t秒。
于是，对于每个节点u，都会保存一个列表，里面记录所有从u出发的边，以及每条边到达的目标节点和耗时。
这样做的目的，是后面从某个节点扩展路径时，可以快速找到它的所有出边。
2. 定义动态规划状态
代码使用一个二维数组来记录状态，含义是：
f[rem][u] 表示：从起点 source 出发，到达节点 u 时，如果剩余电量恰好是 rem，那么累计花费的最小时间是多少。
也就是说，第一维表示剩余电量，第二维表示当前所在节点，值表示最小总时间。
初始化时：
• 在起点
source，一开始剩余电量是power，时间为0；• 所以
f[power][source] = 0；• 其他所有状态都初始化为一个很大的数，表示暂时不可达。
这个状态定义很关键，因为它同时记录了“剩余电量”和“到达节点”，可以区分同样到达某个节点但剩余电量不同的情况。
3. 从高电量向低电量遍历
接下来，代码从剩余电量power开始，一直递减到0，逐层处理。
为什么从高到低？
因为信号每离开一个节点，都会消耗该节点的cost[u]，而cost[u]是正数。所以：
• 从高剩余电量状态出发，只会转移到更低剩余电量的状态；
• 不会从低电量转移到高电量。
因此，按照剩余电量从高到低遍历，可以保证：
• 当处理某个剩余电量
rem时，所有能到达该状态的前驱状态都已经被处理过了；• 用当前状态去更新更低剩余电量的状态，是安全的，不会遗漏或重复。
这本质上是一种按剩余电量分层的动态规划。
4. 每一层剩余电量的处理过程
对于每一个剩余电量rem，代码做两件事：
第一件事：检查是否能到达目标节点
如果f[rem][target]不是无穷大，说明在剩余电量为rem的情况下，可以到达终点target，并且记录了一个总时间。
此时代码会比较这个时间与当前已经记录的全局最小时间minDis：
• 如果
f[rem][target] < minDis，说明找到了更短的到达时间；• 于是更新
minDis为这个更短时间；• 同时把
maxRem更新为当前的剩余电量rem。
由于外层循环是从power递减到0，所以：
• 剩余电量大的状态会先被检查；
• 如果后面出现相同的最小时间，但剩余电量更小，因为判断条件是严格小于，所以不会覆盖；
• 因此最终保留的
maxRem是所有达到最小时间的路径中，剩余电量最大的那个。
这正好满足题目要求：先最小时间，再最大剩余电量。
第二件事：从当前状态向外扩展
接着，代码遍历所有节点x，查看f[rem][x]是否可达。
如果f[rem][x]是无穷大，说明在剩余电量为rem时无法到达节点x，直接跳过。
如果可达，还要判断当前剩余电量rem是否足够支付离开节点x所需的电量，也就是是否满足：
rem >= cost[x]
只有满足这个条件，信号才能从节点x沿任意一条出边继续前进。
如果满足，则计算离开后的剩余电量：
nxtRem = rem - cost[x]
然后遍历节点x的所有出边。对于每一条出边x -> to，耗时为t：
• 当前到达
x的最小时间是f[rem][x]；• 经过这条边后，到达
to的时间是f[rem][x] + t；• 新的剩余电量是
nxtRem；• 如果这个时间比
f[nxtRem][to]原来记录的时间更小，就更新它。
这一步就是所谓的“刷表法”：用当前已经确定的状态，去松弛它能到达的后继状态。
注意：到达某个节点本身不消耗电量，只有离开该节点时才消耗。因此这里是在“准备离开节点x”时扣除cost[x]。
5. 为什么到达 target 后不需要再检查 cost
代码在检查f[rem][target]时，只关心是否能到达终点，并不要求rem >= cost[target]。
这是合理的，因为：
• 信号到达
target后已经完成任务；• 不需要再从
target离开；• 所以不需要支付
cost[target]。
因此，只要某个剩余电量下能到达target，就是一个合法结果。
6. 最终结果判断
当所有剩余电量都处理完后：
• 如果
maxRem仍然是-1，说明从来没有到达过target，返回[-1, -1]；• 否则返回
[minDis, maxRem]，其中：•
minDis是最小总时间；•
maxRem是在这个最小总时间下，到达终点时最大的剩余电量。
对于题目给的例子：
• 路径
0 -> 2 -> 3 -> 4总时间为3；• 消耗电量为
cost[0] + cost[2] + cost[3] = 2 + 1 + 1 = 4；• 初始电量为
4，所以剩余电量为0；• 因此输出
[3, 0]。
这个算法覆盖了所有可能的路径，因为：
• 状态中包含了“当前节点”和“剩余电量”；
• 每次扩展都严格按照消耗电量的规则进行；
• 电量只会减少，所以按电量从高到低处理不会漏掉任何可达状态；
• 对于每个状态，只保留到达该状态的最小时间；
• 最终在全局最小时间的前提下，由于遍历顺序是从高电量到低电量，所以保留的是最大剩余电量。
因此，算法能够得到题目要求的结果。
8. 时间复杂度
设：
• 节点数为
n；• 边数为
m；• 初始电量为
power。
代码外层循环剩余电量，共power + 1次。
每次外层循环中：
• 遍历所有节点，检查状态，复杂度为
O(n)；• 对于可达且满足电量条件的节点，遍历其所有出边，所有出边总和最多为
m，复杂度为O(m)。
所以每一层剩余电量的处理复杂度是O(n + m)。
总时间复杂度为：
O(power * (n + m))
代入题目限制，power <= 1000，n <= 1000，m <= 1000，规模大约在百万级别，是可以接受的。
9. 额外空间复杂度
主要额外空间包括：
• 动态规划状态表
f，大小为(power + 1) * n，所以是O(power * n)；• 邻接表存储图，节点数为
n，边数为m，所以是O(n + m)。
因此总额外空间复杂度为：
O(power * n + n + m)
通常可以简写为：
O(power * n + m)
因为n已经被power * n覆盖。
总结一下：
这个算法用“剩余电量”作为动态规划的一维，用“当前节点”作为另一维，记录到达每个状态的最小时间。然后从高电量到低电量逐层扩展，优先保证总时间最小，再在相同总时间下保留最大剩余电量。时间复杂度为O(power * (n + m))，额外空间复杂度为O(power * n + m)。
Go完整代码如下：
package main
import (
"fmt"
"math"
)
func minTimeMaxPower(n int, edges [][]int, power int, cost []int, source int, target int) []int64 {
type edge struct{ to, t int }
g := make([][]edge, n)
for _, e := range edges {
x, y, t := e[0], e[1], e[2]
g[x] = append(g[x], edge{y, t})
}
f := make([][]int, power+1)
for i := range f {
f[i] = make([]int, n)
for j := range f[i] {
f[i][j] = math.MaxInt
}
}
f[power][source] = 0
minDis, maxRem := math.MaxInt, -1
for rem := power; rem >= 0; rem-- {
if f[rem][target] < minDis {
minDis, maxRem = f[rem][target], rem
}
for x, v := range f[rem] {
if v == math.MaxInt || rem < cost[x] {
continue
}
nxtRem := rem - cost[x]
for _, e := range g[x] {
f[nxtRem][e.to] = min(f[nxtRem][e.to], v+e.t) // 刷表法
}
}
}
if maxRem < 0 {
return []int64{-1, -1}
}
return []int64{int64(minDis), int64(maxRem)}
}func main() {
n := 5
edges := [][]int{{0, 1, 1}, {1, 4, 1}, {0, 2, 1}, {2, 3, 1}, {3, 4, 1}}
power := 4
cost := []int{2, 3, 1, 1, 1}
source := 0
target := 4
result := minTimeMaxPower(n, edges, power, cost, source, target)
fmt.Println(result)
}
Python完整代码如下：
# -*-coding:utf-8-*-
from typing import List
def minTimeMaxPower(
n: int,
edges: List[List[int]],
power: int,
cost: List[int],
source: int,
target: int
) -> List[int]:
g = [[] for _ in range(n)]
for u, v, t in edges:
g[u].append((v, t))
INF = 10**30
f = [[INF] * n for _ in range(power + 1)]
f[power][source] = 0
min_dis = INF
max_rem = -1
for rem in range(power, -1, -1):
if f[rem][target] < min_dis:
min_dis = f[rem][target]
max_rem = rem
for x, cur_time in enumerate(f[rem]):
if cur_time == INF or rem < cost[x]:
continue
nxt_rem = rem - cost[x]
for to, t in g[x]:
new_time = cur_time + t
if new_time < f[nxt_rem][to]:
f[nxt_rem][to] = new_time
if max_rem < 0:
return [-1, -1]
return [min_dis, max_rem]
if __name__ == "__main__":
n = 5
edges = [[0, 1, 1], [1, 4, 1], [0, 2, 1], [2, 3, 1], [3, 4, 1]]
power = 4
cost = [2, 3, 1, 1, 1]
source = 0
target = 4result = minTimeMaxPower(n, edges, power, cost, source, target)
print(result)
C++完整代码如下：
using namespace std;vector minTimeMaxPower(
int n,
vector int >>& edges,
int power,
vector< int >& cost,
int source,
int target
) {
struct Edge {
int to, t;
};
vector > g(n);
for (auto& e : edges) {
int x = e[ 0 ], y = e[ 1 ], t = e[ 2 ];
g[x].push_back({y, t});
}
const long long INF = LLONG_MAX / 4 ;
// f[rem][u] 表示到达节点 u 且剩余电量为 rem 时的最小时间
vector > f(power + 1 , vector (n, INF));
f[power][source] = 0 ;
long long minDis = INF;
int maxRem = -1 ;
for ( int rem = power; rem >= 0 ; --rem) {
if (f[rem][target] < minDis) {
minDis = f[rem][target];
maxRem = rem;
}
for ( int x = 0 ; x < n; ++x) {
long long curTime = f[rem][x];
if (curTime == INF || rem < cost[x]) {
continue ;
}
int nxtRem = rem - cost[x];
for (auto& e : g[x]) {
if (curTime + e.t < f[nxtRem][e.to]) {
f[nxtRem][e.to] = curTime + e.t;
}
}
}
}
if (maxRem < 0 ) {
return { -1 , -1 };
}
return {minDis, (long long)maxRem};
}
int main() {
int n = 5 ;
vector int >> edges = {
{ 0 , 1 , 1 },
{ 1 , 4 , 1 },
{ 0 , 2 , 1 },
{ 2 , 3 , 1 },
{ 3 , 4 , 1 }
};
int power = 4 ;
vector< int > cost = { 2 , 3 , 1 , 1 , 1 };
int source = 0 ;
int target = 4 ;
vector result = minTimeMaxPower(n, edges, power, cost, source, target);
cout << "[" << result[ 0 ] << ", " << result[ 1 ] << "]" << endl;
return 0 ;
}
我们相信人工智能为普通人提供了一种“增强工具”，并致力于分享全方位的AI知识。在这里，您可以找到最新的AI科普文章、工具评测、提升效率的秘籍以及行业洞察。 欢迎关注“福大大架构师每日一题”，发消息可获得面试资料，让AI助力您的未来发展。
热门跟贴