2026-10-02有限電量到達目標節(jié)點的最少時間。用go語言給定一張包含 n 個頂點的帶權有向圖頂點編號為 0 到 n-1。圖中的邊由 edges 表示每條邊 [u, v, t] 表示從頂點 u 指向頂點 v經過這條邊需要耗時 t 秒。另有一個初始電量 power、一個長度為 n 的數(shù)組 cost以及起點 source 和終點 target。cost[u] 表示信號要從頂點 u 沿任意一條出邊繼續(xù)發(fā)送時需要消耗的電量。信號在第 0 秒從 source 出發(fā)初始電量為 power。到達某個頂點時不會扣電只有當信號準備離開該頂點、沿某條出邊繼續(xù)前進時才需要先保證當前剩余電量不少于 cost[u]然后剩余電量減少 cost[u]。每經過一條邊累計時間增加這條邊的耗時?，F(xiàn)在要求計算信號從 source 到 target 的可行路徑。優(yōu)先使到達 target 的總時間最小如果存在多條路徑都能達到這個最小總時間則選擇到達 target 時剩余電量最大的那條路徑。返回一個包含兩個整數(shù)的結果第一個是最小總時間第二個是該最小總時間下的最大剩余電量。如果信號無法到達 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]。解釋信號從節(jié)點 0 出發(fā)擁有 4 個單位的電量。路徑 0 - 1 - 4 無效因為離開節(jié)點 0 后信號剩余 2 個單位的電量這小于 cost[1] 3。有效路徑 0 - 2 - 3 - 4 總共花費時間為 3。沿著這條路徑消耗的總電量為 cost[0] cost[2] cost[3] 4剩余電量為 0。因此答案為 [3, 0]。題目來自力扣3977。1. 把圖整理成鄰接表首先代碼把輸入的邊數(shù)組edges轉換成鄰接表。每一條邊[u, v, t]表示從節(jié)點u出發(fā)可以到達節(jié)點v經過這條邊需要花費t秒。于是對于每個節(jié)點u都會保存一個列表里面記錄所有從u出發(fā)的邊以及每條邊到達的目標節(jié)點和耗時。這樣做的目的是后面從某個節(jié)點擴展路徑時可以快速找到它的所有出邊。2. 定義動態(tài)規(guī)劃狀態(tài)代碼使用一個二維數(shù)組來記錄狀態(tài)含義是f[rem][u]表示從起點source出發(fā)到達節(jié)點u時如果剩余電量恰好是rem那么累計花費的最小時間是多少。也就是說第一維表示剩余電量第二維表示當前所在節(jié)點值表示最小總時間。初始化時在起點source一開始剩余電量是power時間為0所以f[power][source] 0其他所有狀態(tài)都初始化為一個很大的數(shù)表示暫時不可達。這個狀態(tài)定義很關鍵因為它同時記錄了“剩余電量”和“到達節(jié)點”可以區(qū)分同樣到達某個節(jié)點但剩余電量不同的情況。3. 從高電量向低電量遍歷接下來代碼從剩余電量power開始一直遞減到0逐層處理。為什么從高到低因為信號每離開一個節(jié)點都會消耗該節(jié)點的cost[u]而cost[u]是正數(shù)。所以從高剩余電量狀態(tài)出發(fā)只會轉移到更低剩余電量的狀態(tài)不會從低電量轉移到高電量。因此按照剩余電量從高到低遍歷可以保證當處理某個剩余電量rem時所有能到達該狀態(tài)的前驅狀態(tài)都已經被處理過了用當前狀態(tài)去更新更低剩余電量的狀態(tài)是安全的不會遺漏或重復。這本質上是一種按剩余電量分層的動態(tài)規(guī)劃。4. 每一層剩余電量的處理過程對于每一個剩余電量rem代碼做兩件事第一件事檢查是否能到達目標節(jié)點如果f[rem][target]不是無窮大說明在剩余電量為rem的情況下可以到達終點target并且記錄了一個總時間。此時代碼會比較這個時間與當前已經記錄的全局最小時間minDis如果f[rem][target] minDis說明找到了更短的到達時間于是更新minDis為這個更短時間同時把maxRem更新為當前的剩余電量rem。由于外層循環(huán)是從power遞減到0所以剩余電量大的狀態(tài)會先被檢查如果后面出現(xiàn)相同的最小時間但剩余電量更小因為判斷條件是嚴格小于所以不會覆蓋因此最終保留的maxRem是所有達到最小時間的路徑中剩余電量最大的那個。這正好滿足題目要求先最小時間再最大剩余電量。第二件事從當前狀態(tài)向外擴展接著代碼遍歷所有節(jié)點x查看f[rem][x]是否可達。如果f[rem][x]是無窮大說明在剩余電量為rem時無法到達節(jié)點x直接跳過。如果可達還要判斷當前剩余電量rem是否足夠支付離開節(jié)點x所需的電量也就是是否滿足rem cost[x]只有滿足這個條件信號才能從節(jié)點x沿任意一條出邊繼續(xù)前進。如果滿足則計算離開后的剩余電量nxtRem rem - cost[x]然后遍歷節(jié)點x的所有出邊。對于每一條出邊x - to耗時為t當前到達x的最小時間是f[rem][x]經過這條邊后到達to的時間是f[rem][x] t新的剩余電量是nxtRem如果這個時間比f[nxtRem][to]原來記錄的時間更小就更新它。這一步就是所謂的“刷表法”用當前已經確定的狀態(tài)去松弛它能到達的后繼狀態(tài)。注意到達某個節(jié)點本身不消耗電量只有離開該節(jié)點時才消耗。因此這里是在“準備離開節(jié)點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. 正確性簡要說明這個算法覆蓋了所有可能的路徑因為狀態(tài)中包含了“當前節(jié)點”和“剩余電量”每次擴展都嚴格按照消耗電量的規(guī)則進行電量只會減少所以按電量從高到低處理不會漏掉任何可達狀態(tài)對于每個狀態(tài)只保留到達該狀態(tài)的最小時間最終在全局最小時間的前提下由于遍歷順序是從高電量到低電量所以保留的是最大剩余電量。因此算法能夠得到題目要求的結果。8. 時間復雜度設節(jié)點數(shù)為n邊數(shù)為m初始電量為power。代碼外層循環(huán)剩余電量共power 1次。每次外層循環(huán)中遍歷所有節(jié)點檢查狀態(tài)復雜度為O(n)對于可達且滿足電量條件的節(jié)點遍歷其所有出邊所有出邊總和最多為m復雜度為O(m)。所以每一層剩余電量的處理復雜度是O(n m)?？倳r間復雜度為O(power * (n m))代入題目限制power 1000n 1000m 1000規(guī)模大約在百萬級別是可以接受的。9. 額外空間復雜度主要額外空間包括動態(tài)規(guī)劃狀態(tài)表f大小為(power 1) * n所以是O(power * n)鄰接表存儲圖節(jié)點數(shù)為n邊數(shù)為m所以是O(n m)。因此總額外空間復雜度為O(power * n n m)通?？梢院唽憺镺(power * n m)因為n已經被power * n覆蓋?？偨Y一下這個算法用“剩余電量”作為動態(tài)規(guī)劃的一維用“當前節(jié)點”作為另一維記錄到達每個狀態(tài)的最小時間。然后從高電量到低電量逐層擴展優(yōu)先保證總時間最小再在相同總時間下保留最大剩余電量。時間復雜度為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] 表示到達節(jié)點 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;}