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

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 = 4

     result = 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助力您的未来发展。