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 1000n 1000m 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(fmtmath)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,power1)fori:rangef{f[i]make([]int,n)forj:rangef[i]{f[i][j]math.MaxInt}}f[power][source]0minDis,maxRem:math.MaxInt,-1forrem:power;rem0;rem--{iff[rem][target]minDis{minDis,maxRemf[rem][target],rem}forx,v:rangef[rem]{ifvmath.MaxInt||remcost[x]{continue}nxtRem:rem-cost[x]for_,e:rangeg[x]{f[nxtRem][e.to]min(f[nxtRem][e.to],ve.t)// 刷表法}}}ifmaxRem0{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))INF10**30f[[INF]*nfor_inrange(power1)]f[power][source]0min_disINF max_rem-1forreminrange(power,-1,-1):iff[rem][target]min_dis:min_disf[rem][target]max_remremforx,cur_timeinenumerate(f[rem]):ifcur_timeINForremcost[x]:continuenxt_remrem-cost[x]forto,ting[x]:new_timecur_timetifnew_timef[nxt_rem][to]:f[nxt_rem][to]new_timeifmax_rem0:return[-1,-1]return[min_dis,max_rem]if__name____main__:n5edges[[0,1,1],[1,4,1],[0,2,1],[2,3,1],[3,4,1]]power4cost[2,3,1,1,1]source0target4resultminTimeMaxPower(n,edges,power,cost,source,target)print(result)C完整代码如下#includebits/stdc.husingnamespacestd;vectorlonglongminTimeMaxPower(intn,vectorvectorintedges,intpower,vectorintcost,intsource,inttarget){structEdge{intto,t;};vectorvectorEdgeg(n);for(autoe:edges){intxe[0],ye[1],te[2];g[x].push_back({y,t});}constlonglongINFLLONG_MAX/4;// f[rem][u] 表示到达节点 u 且剩余电量为 rem 时的最小时间vectorvectorlonglongf(power1,vectorlonglong(n,INF));f[power][source]0;longlongminDisINF;intmaxRem-1;for(intrempower;rem0;--rem){if(f[rem][target]minDis){minDisf[rem][target];maxRemrem;}for(intx0;xn;x){longlongcurTimef[rem][x];if(curTimeINF||remcost[x]){continue;}intnxtRemrem-cost[x];for(autoe:g[x]){if(curTimee.tf[nxtRem][e.to]){f[nxtRem][e.to]curTimee.t;}}}}if(maxRem0){return{-1,-1};}return{minDis,(longlong)maxRem};}intmain(){intn5;vectorvectorintedges{{0,1,1},{1,4,1},{0,2,1},{2,3,1},{3,4,1}};intpower4;vectorintcost{2,3,1,1,1};intsource0;inttarget4;vectorlonglongresultminTimeMaxPower(n,edges,power,cost,source,target);cout[result[0], result[1]]endl;return0;}