2026-10-02：有限电量到达目标节点的最少时间。用go语言，给定一张包含 n 个顶点的带权有向图，顶点编号为 0 到 n-1。图中的边由 edges 表示，每条边 [u, v, t] 表示从顶点

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]。

7. 正确性简要说明

这个算法覆盖了所有可能的路径，因为：

• 状态中包含了“当前节点”和“剩余电量”；
• 每次扩展都严格按照消耗电量的规则进行；
• 电量只会减少，所以按电量从高到低处理不会漏掉任何可达状态；
• 对于每个状态，只保留到达该状态的最小时间；
• 最终在全局最小时间的前提下，由于遍历顺序是从高电量到低电量，所以保留的是最大剩余电量。

因此，算法能够得到题目要求的结果。

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完整代码如下：

packagemainimport("fmt""math")funcminTimeMaxPower(nint,edges[][]int,powerint,cost[]int,sourceint,targetint)[]int64{typeedgestruct{to,tint}g:=make([][]edge,n)for_,e:=rangeedges{x,y,t:=e[0],e[1],e[2]g[x]=append(g[x],edge{y,t})}f:=make([][]int,power+1)fori:=rangef{f[i]=make([]int,n)forj:=rangef[i]{f[i][j]=math.MaxInt}}f[power][source]=0minDis,maxRem:=math.MaxInt,-1forrem:=power;rem>=0;rem--{iff[rem][target]<minDis{minDis,maxRem=f[rem][target],rem}forx,v:=rangef[rem]{ifv==math.MaxInt||rem<cost[x]{continue}nxtRem:=rem-cost[x]for_,e:=rangeg[x]{f[nxtRem][e.to]=min(f[nxtRem][e.to],v+e.t)// 刷表法}}}ifmaxRem<0{return[]int64{-1,-1}}return[]int64{int64(minDis),int64(maxRem)}}funcmain(){n:=5edges:=[][]int{{0,1,1},{1,4,1},{0,2,1},{2,3,1},{3,4,1}}power:=4cost:=[]int{2,3,1,1,1}source:=0target:=4result:=minTimeMaxPower(n,edges,power,cost,source,target)fmt.Println(result)}

Python完整代码如下：

# -*-coding:utf-8-*-fromtypingimportListdefminTimeMaxPower(n:int,edges:List[List[int]],power:int,cost:List[int],source:int,target:int)->List[int]:g=[[]for_inrange(n)]foru,v,tinedges:g[u].append((v,t))INF=10**30f=[[INF]*nfor_inrange(power+1)]f[power][source]=0min_dis=INF max_rem=-1forreminrange(power,-1,-1):iff[rem][target]<min_dis:min_dis=f[rem][target]max_rem=remforx,cur_timeinenumerate(f[rem]):ifcur_time==INForrem<cost[x]:continuenxt_rem=rem-cost[x]forto,ting[x]:new_time=cur_time+tifnew_time<f[nxt_rem][to]:f[nxt_rem][to]=new_timeifmax_rem<0:return[-1,-1]return[min_dis,max_rem]if__name__=="__main__":n=5edges=[[0,1,1],[1,4,1],[0,2,1],[2,3,1],[3,4,1]]power=4cost=[2,3,1,1,1]source=0target=4result=minTimeMaxPower(n,edges,power,cost,source,target)print(result)

C++完整代码如下：

#include<bits/stdc++.h>usingnamespacestd;vector<longlong>minTimeMaxPower(intn,vector<vector<int>>&edges,intpower,vector<int>&cost,intsource,inttarget){structEdge{intto,t;};vector<vector<Edge>>g(n);for(auto&e:edges){intx=e[0],y=e[1],t=e[2];g[x].push_back({y,t});}constlonglongINF=LLONG_MAX/4;// f[rem][u] 表示到达节点 u 且剩余电量为 rem 时的最小时间vector<vector<longlong>>f(power+1,vector<longlong>(n,INF));f[power][source]=0;longlongminDis=INF;intmaxRem=-1;for(intrem=power;rem>=0;--rem){if(f[rem][target]<minDis){minDis=f[rem][target];maxRem=rem;}for(intx=0;x<n;++x){longlongcurTime=f[rem][x];if(curTime==INF||rem<cost[x]){continue;}intnxtRem=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,(longlong)maxRem};}intmain(){intn=5;vector<vector<int>>edges={{0,1,1},{1,4,1},{0,2,1},{2,3,1},{3,4,1}};intpower=4;vector<int>cost={2,3,1,1,1};intsource=0;inttarget=4;vector<longlong>result=minTimeMaxPower(n,edges,power,cost,source,target);cout<<"["<<result[0]<<", "<<result[1]<<"]"<<endl;return0;}