2026-08-19：有限重边的最小阈值路径。用go语言，有一个包含 n 个顶点的带权无向图，顶点编号从 0 到 n-1。每条边连接两个顶点，并带有一

2026-08-19：有限重边的最小阈值路径。用go语言，有一个包含 n 个顶点的带权无向图，顶点编号从 0 到 n-1。每条边连接两个顶点，并带有一个整数权值。

给定起点 source、终点 target 和一个非负整数 k。对于任意选定的整数阈值，如果某条边的权值不超过该阈值，就把它看作轻边；如果权值超过阈值，就把它看作重边。

一条从 source 到 target 的路径，如果其中包含的重边数量不超过 k，那么这条路径就是有效的。

问题是：找出一个最小的整数阈值，使得从 source 到 target 至少存在一条有效路径。如果不存在这样的阈值，就返回 -1。

1 <= n <= 1000。

0 <= edges.length <= 1000。

edges[i] = [ui, vi, wi]。

0 <= ui, vi <= n - 1。

1 <= wi <= 1000000000。

0 <= source, target <= n - 1。

0 <= k <= edges.length。

输入： n = 6, edges = [[0,1,5],[1,2,3],[3,4,4],[4,5,1],[1,4,2]], source = 0, target = 3, k = 1。

输出： 4。

解释：

使得从节点 0 到节点 3 的路径最多使用 1 条重边的最小 threshold 为 4。

轻边：[1, 2, 3], [3, 4, 4], [4, 5, 1], [1, 4, 2]。

重边：[0, 1, 5]。

一条有效路径是 0 → 1 → 4 → 3。它只使用了 1 条重边（[0, 1, 5]），满足限制 k = 1。

任何更小的 threshold 都会导致无法在不超过 1 条重边的情况下到达节点 3。

题目来自力扣3924。

一、建图并确定二分上界

1. 1. 用一个邻接表保存无向图。每条边以(目标节点, 权重)的形式存储，并且无向边会正反存两次。

2. 2. 遍历所有边时，记录图中最大的边权maxWt。

3. 3. 二分查找的候选阈值范围是[0, maxWt]。
   因为当阈值取到maxWt时，所有边的权重都不超过阈值，全部变成轻边。此时只要图连通，路径一定不会包含重边，自然满足限制。
   如果连threshold = maxWt都不存在有效路径，那说明图本身不连通，或者由于其它原因无法满足要求，最终会返回-1。

定义一个布尔函数check(threshold)，表示在当前阈值下，是否存在一条从source到target的路径，且路径上的重边数量不超过k。

这个函数具有单调性：

• • 阈值越大，被判定为轻边的边越多，被判定为重边的边越少；

• • 因此任意一条路径的重边数量只会减少或不变，不会增加；

• • 所以check(threshold)会从某个阈值开始由false变为true，之后一直保持true。

基于这种单调性，可以用二分查找在[0, maxWt]中找到第一个满足check的阈值，这个阈值就是答案。

三、固定阈值下的判断过程

对于某个固定的阈值threshold，内部的任务是：
把每条边看成一个代价：

• • 如果边权w <= threshold，代价为0，称为轻边；

• • 如果边权w > threshold，代价为1，称为重边。

于是问题转化为：
计算从source到各个节点的“最少重边数”，也就是边权为0或1的最短路。

代码使用了一个类似0-1 BFS的方法。

1. 初始化

• • 距离数组dis[i]表示从source到节点i最少需要经过多少条重边。

• • 初始时所有dis[i]设为极大值，只有dis[source] = 0。

• • 准备两个容器：

• • •ql：用切片模拟栈，后进先出，用来存放通过轻边到达的节点；

  • •qr：用切片模拟队列，先进先出，用来存放通过重边到达的节点。

• • 初始把(source, 0)放入ql。

循环条件：ql或qr中至少有一个不为空。

每次优先从ql的末尾取出一个元素，也就是栈顶；
如果ql为空，才从qr的头部取出一个元素，也就是队首。

取出的元素包含：

• • 当前节点x；

• • 从source到x已经累计的重边数量d。

如果当前节点x正好是target，说明已经找到一条满足限制的路径，因为能够进入容器的节点的重边数一定没有超过k。此时直接返回true。

4. 跳过过期记录

如果当前记录中的重边数d大于已经记录的最优值dis[x]，说明这条记录是之前某个较差的路径留下的，直接跳过，避免重复扩展。

5. 扩展邻接边

遍历当前节点x的所有相邻边(y, w)：

• • 根据w和threshold的大小关系决定这条边的代价cost：

• • •w <= threshold：轻边，cost = 0；

  • •w > threshold：重边，cost = 1。

• • 计算从source经过x再到y的重边总数：
  newDis = d + cost。

• • 如果newDis < dis[y]，说明找到了一条到达y的更好路径：

• • • 更新dis[y] = newDis。

  • • 如果这条边是轻边，即cost == 0，说明没有增加重边，将(y, newDis)放入ql的栈顶，以便之后优先处理；

  • • 如果这条边是重边，即cost == 1，并且newDis <= k，说明还没超过限制，将(y, newDis)放入qr的队尾。

这样做可以保证：

• • 轻边不会增加重边数，因此会被优先处理，帮助更快地传播最小重边数；

• • 重边会增加一条重边，放入队列尾部，稍后处理；

• • 重边数超过k的状态不会进入队列，从而避免无效搜索。

如果队列全部处理完，仍然没有到达target，说明在当前阈值下不存在不超过k条重边的有效路径，返回false。

四、二分结果

二分查找结束后，会得到第一个使check返回true的阈值。

• • 如果这个阈值小于等于maxWt，它就是要求的最小阈值；

• • 如果结果大于maxWt，说明所有候选阈值都无效，返回-1。

对于题目示例：

• •threshold = 4时：

• • • 边[0,1,5]是重边；

  • • 边[1,4,2]、[4,3,4]是轻边；

  • • 路径0 → 1 → 4 → 3只包含一条重边，满足k = 1；

• • 任何小于4的阈值都会使更多边变成重边，无法在一条重边以内到达target。

因此答案是4。

五、时间复杂度

• • 二分查找的候选范围是[0, maxWt]，最大边权maxWt可能达到10^9，因此二分次数约为O(log maxWt)，大约 30 次左右。

• • 每次check内部相当于执行一次边权为0或1的最短路计算，需要访问所有节点和边，复杂度为O(n + m)，其中n是节点数，m是边数。

因此总时间复杂度为：

O((n + m) log maxWt)

六、额外空间复杂度

• • 邻接表存储所有边，占用O(n + m)空间；

• • 距离数组dis占用O(n)空间；

• • 两个容器ql和qr最多存放O(n)个元素。

所以总的额外空间复杂度为：

O(n + m)

Go完整代码如下：

package main

 import (
    "fmt"
    "math"
    "sort"
)

 func minimumThreshold(n int, edges [][]int, source int, target int, k int) int {
    type edge struct{ to, wt int }
    g := make([][]edge, n)
    maxWt := 0
    for _, e := range edges {
        x, y, wt := e[0], e[1], e[2]
        g[x] = append(g[x], edge{y, wt})
        g[y] = append(g[y], edge{x, wt})
        maxWt = max(maxWt, wt)
    }

     dis := make([]int, n)
    ans := sort.Search(maxWt+1, func(threshold int) bool {
        for i := range dis {
            dis[i] = math.MaxInt
        }
        dis[source] = 0

         type pair struct{ x, d int }
        ql, qr := []pair{{source, dis[source]}}, []pair{} // 模拟双端队列

         for len(ql) > 0 || len(qr) > 0 {
            var p pair
            if len(ql) > 0 {
                ql, p = ql[:len(ql)-1], ql[len(ql)-1] // 队首出
            } else {
                p, qr = qr[0], qr[1:] // 队尾出
            }

             x := p.x
            if x == target {
                return true
            }

             if p.d > dis[x] {
                continue
            }

             for _, e := range g[x] {
                y := e.to
                wt := 0
                if e.wt > threshold {
                    wt = 1
                }
                newDis := p.d + wt
                if newDis < dis[y] {
                    dis[y] = newDis
                    if wt == 0 {
                        ql = append(ql, pair{y, newDis}) // 加到队首
                    } else if newDis <= k {
                        qr = append(qr, pair{y, newDis}) // 加到队尾
                    }
                }
            }
        }

         return false
    })

     if ans > maxWt { // 图不连通
        return -1
    }
    return ans
}

 func main() {
    n := 6
    edges := [][]int{{0, 1, 5}, {1, 2, 3}, {3, 4, 4}, {4, 5, 1}, {1, 4, 2}}
    source := 0
    target := 3
    k := 1
    result := minimumThreshold(n, edges, source, target, k)
    fmt.Println(result)
}

Python完整代码如下：

# -*-coding:utf-8-*-

 from collections import deque

 def minimumThreshold(n, edges, source, target, k):
    # 构建邻接表
    graph = [[] for _ in range(n)]
    max_weight = 0
    for u, v, w in edges:
        graph[u].append((v, w))
        graph[v].append((u, w))
        max_weight = max(max_weight, w)

     # 检查给定 threshold 下是否存在有效路径
    def check(threshold):
        # dist[x] 表示从 source 到 x 最少经过的重边数量
        dist = [float('inf')] * n
        dist[source] = 0
        dq = deque([source])

         while dq:
            x = dq.popleft()
            if x == target:
                return True
            for y, w in graph[x]:
                cost = 0 if w <= threshold else 1
                nd = dist[x] + cost
                if nd < dist[y] and nd <= k:
                    dist[y] = nd
                    if cost == 0:
                        dq.appendleft(y)   # 轻边，权重为0，插入队首
                    else:
                        dq.append(y)       # 重边，权重为1，插入队尾
        return False

     # 二分查找最小的 threshold
    ans = max_weight + 1
    left, right = 0, max_weight
    while left <= right:
        mid = (left + right) // 2
        if check(mid):
            ans = mid
            right = mid - 1
        else:
            left = mid + 1

     return -1 if ans > max_weight else ans

 if __name__ == "__main__":
    n = 6
    edges = [[0, 1, 5], [1, 2, 3], [3, 4, 4], [4, 5, 1], [1, 4, 2]]
    source = 0
    target = 3
    k = 1
    result = minimumThreshold(n, edges, source, target, k)
    print(result)

C++完整代码如下：

  

  

  

  

  


 using namespace std;

 int minimumThreshold(int n, vector 
 
 int 
 >>& edges,  
 int 
  source,  
 int 
  target,  
 int 
  k) { 
 
 
      
 // 构建邻接表 
 
 
     vector 
 
 int 
 ,  
 int 
 >>> graph(n); 
 
 
      
 int 
  maxWeight =  
 0 
 ; 
 
 
      
 for 
  (auto& e : edges) { 
 
 
          
 int 
  u = e[ 
 0 
 ], v = e[ 
 1 
 ], w = e[ 
 2 
 ]; 
 
 
         graph[u].push_back({v, w}); 
 
 
         graph[v].push_back({u, w}); 
 
 
         maxWeight = max(maxWeight, w); 
 
 
     } 
 
 
 
 
      
 // 检查给定 threshold 下是否存在有效路径 
 
 
     auto check = [&]( 
 int 
  threshold) ->  
 bool 
  { 
 
 
         vector< 
 int 
 > dist(n, INT_MAX); 
 
 
         dist[source] =  
 0 
 ; 
 
 
 
 
          
 // ql 模拟栈（后进先出），处理轻边；qr 模拟队列（先进先出），处理重边 
 
 
         vector 
 
 int 
 ,  
 int 
 >> ql;           
 // 栈 
 
 
         queue 
 
 int 
 ,  
 int 
 >> qr;            
 // 队列 
 
 
         ql.push_back({source,  
 0 
 }); 
 
 
 
 
         while (!ql.empty() || !qr.empty()) { 
 
 
             pair< 
 int 
 ,  
 int 
 > p; 
 
 
              
 if 
  (!ql.empty()) { 
 
 
                 p = ql.back(); 
 
 
                 ql.pop_back();               
 // 从栈顶取出 
 
 
             }  
 else 
  { 
 
 
                 p = qr.front(); 
 
 
                 qr.pop();                    
 // 从队首取出 
 
 
             } 
 
 
 
 
              
 int 
  x = p.first; 
 
 
              
 int 
  d = p.second; 
 
 
 
 
              
 if 
  (x == target) { 
 
 
                  
 return 
   
 true 
 ; 
 
 
             } 
 
 
 
 
              
 if 
  (d > dist[x]) { 
 
 
                  
 continue 
 ;                    
 // 不是最优距离，跳过 
 
 
             } 
 
 
 
 
              
 for 
  (auto& edge : graph[x]) { 
 
 
                  
 int 
  y = edge.first; 
 
 
                  
 int 
  w = edge.second; 
 
 
                  
 int 
  cost = (w > threshold) ?  
 1 
  :  
 0 
 ; 
 
 
                  
 int 
  nd = d + cost; 
 
 
                  
 if 
  (nd < dist[y]) { 
 
 
                     dist[y] = nd; 
 
 
                      
 if 
  (cost ==  
 0 
 ) { 
 
 
                         ql.push_back({y, nd});       
 // 轻边，放入栈 
 
 
                     }  
 else 
   
 if 
  (nd <= k) { 
 
 
                         qr.push({y, nd});            
 // 重边，放入队列 
 
 
                     } 
 
 
                 } 
 
 
             } 
 
 
         } 
 
 
          
 return 
   
 false 
 ; 
 
 
     }; 
 
 
 
 
      
 // 二分查找最小的 threshold 
 
 
      
 int 
  left =  
 0 
 , right = maxWeight; 
 
 
      
 int 
  ans = maxWeight +  
 1 
 ;     
 // 初始化为不可能的值 
 
 
     while (left <= right) { 
 
 
          
 int 
  mid = left + (right - left) /  
 2 
 ; 
 
 
          
 if 
  (check(mid)) { 
 
 
             ans = mid; 
 
 
             right = mid -  
 1 
 ; 
 
 
         }  
 else 
  { 
 
 
             left = mid +  
 1 
 ; 
 
 
         } 
 
 
     } 
 
 
 
 
      
 return 
  (ans > maxWeight) ?  
 -1 
  : ans; 
 
 
 } 
 
 
 
 
 int 
  main() { 
 
 
      
 int 
  n =  
 6 
 ; 
 
 
     vector 
 
 int 
 >> edges = { 
 
 
         { 
 0 
 ,  
 1 
 ,  
 5 
 }, 
 
 
         { 
 1 
 ,  
 2 
 ,  
 3 
 }, 
 
 
         { 
 3 
 ,  
 4 
 ,  
 4 
 }, 
 
 
         { 
 4 
 ,  
 5 
 ,  
 1 
 }, 
 
 
         { 
 1 
 ,  
 4 
 ,  
 2 
 } 
 
 
     }; 
 
 
      
 int 
  source =  
 0 
 ; 
 
 
      
 int 
  target =  
 3 
 ; 
 
 
      
 int 
  k =  
 1 
 ; 
 
 
 
 
      
 int 
  result = minimumThreshold(n, edges, source, target, k); 
 
 
     cout << result << endl; 
 
 
 
 
      
 return 
   
 0 
 ; 
 
 
 } 
 
 
 
 
 
 
 

我们相信人工智能为普通人提供了一种“增强工具”，并致力于分享全方位的AI知识。在这里，您可以找到最新的AI科普文章、工具评测、提升效率的秘籍以及行业洞察。 欢迎关注“福大大架构师每日一题”，发消息可获得面试资料，让AI助力您的未来发展。