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. 用一个邻接表保存无向图。每条边以
(目标节点, 权重)的形式存储，并且无向边会正反存两次。2. 遍历所有边时，记录图中最大的边权
maxWt。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 ansif __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助力您的未来发展。
热门跟贴