2026-08-19有限重边的最小阈值路径。用go语言有一个包含 n 个顶点的带权无向图顶点编号从 0 到 n-1。每条边连接两个顶点并带有一个整数权值。给定起点 source、终点 target 和一个非负整数 k。对于任意选定的整数阈值如果某条边的权值不超过该阈值就把它看作轻边如果权值超过阈值就把它看作重边。一条从 source 到 target 的路径如果其中包含的重边数量不超过 k那么这条路径就是有效的。问题是找出一个最小的整数阈值使得从 source 到 target 至少存在一条有效路径。如果不存在这样的阈值就返回 -1。1 n 1000。0 edges.length 10​​​​​​00。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。一、建图并确定二分上界用一个邻接表保存无向图。每条边以(目标节点, 权重)的形式存储并且无向边会正反存两次。遍历所有边时记录图中最大的边权maxWt。二分查找的候选阈值范围是[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。2. 不断取出节点处理循环条件ql或qr中至少有一个不为空。每次优先从ql的末尾取出一个元素也就是栈顶如果ql为空才从qr的头部取出一个元素也就是队首。取出的元素包含当前节点x从source到x已经累计的重边数量d。3. 判断是否到达目标如果当前节点x正好是target说明已经找到一条满足限制的路径因为能够进入容器的节点的重边数一定没有超过k。此时直接返回true。4. 跳过过期记录如果当前记录中的重边数d大于已经记录的最优值dis[x]说明这条记录是之前某个较差的路径留下的直接跳过避免重复扩展。5. 扩展邻接边遍历当前节点x的所有相邻边(y, w)根据w和threshold的大小关系决定这条边的代价costw threshold轻边cost 0w 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的状态不会进入队列从而避免无效搜索。6. 循环结束如果队列全部处理完仍然没有到达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完整代码如下packagemainimport(fmtmathsort)funcminimumThreshold(nint,edges[][]int,sourceint,targetint,kint)int{typeedgestruct{to,wtint}g:make([][]edge,n)maxWt:0for_,e:rangeedges{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})maxWtmax(maxWt,wt)}dis:make([]int,n)ans:sort.Search(maxWt1,func(thresholdint)bool{fori:rangedis{dis[i]math.MaxInt}dis[source]0typepairstruct{x,dint}ql,qr:[]pair{{source,dis[source]}},[]pair{}// 模拟双端队列forlen(ql)0||len(qr)0{varp pairiflen(ql)0{ql,pql[:len(ql)-1],ql[len(ql)-1]// 队首出}else{p,qrqr[0],qr[1:]// 队尾出}x:p.xifxtarget{returntrue}ifp.ddis[x]{continue}for_,e:rangeg[x]{y:e.to wt:0ife.wtthreshold{wt1}newDis:p.dwtifnewDisdis[y]{dis[y]newDisifwt0{qlappend(ql,pair{y,newDis})// 加到队首}elseifnewDisk{qrappend(qr,pair{y,newDis})// 加到队尾}}}}returnfalse})ifansmaxWt{// 图不连通return-1}returnans}funcmain(){n:6edges:[][]int{{0,1,5},{1,2,3},{3,4,4},{4,5,1},{1,4,2}}source:0target:3k:1result:minimumThreshold(n,edges,source,target,k)fmt.Println(result)}Python完整代码如下# -*-coding:utf-8-*-fromcollectionsimportdequedefminimumThreshold(n,edges,source,target,k):# 构建邻接表graph[[]for_inrange(n)]max_weight0foru,v,winedges:graph[u].append((v,w))graph[v].append((u,w))max_weightmax(max_weight,w)# 检查给定 threshold 下是否存在有效路径defcheck(threshold):# dist[x] 表示从 source 到 x 最少经过的重边数量dist[float(inf)]*n dist[source]0dqdeque([source])whiledq:xdq.popleft()ifxtarget:returnTruefory,wingraph[x]:cost0ifwthresholdelse1nddist[x]costifnddist[y]andndk:dist[y]ndifcost0:dq.appendleft(y)# 轻边权重为0插入队首else:dq.append(y)# 重边权重为1插入队尾returnFalse# 二分查找最小的 thresholdansmax_weight1left,right0,max_weightwhileleftright:mid(leftright)//2ifcheck(mid):ansmid rightmid-1else:leftmid1return-1ifansmax_weightelseansif__name____main__:n6edges[[0,1,5],[1,2,3],[3,4,4],[4,5,1],[1,4,2]]source0target3k1resultminimumThreshold(n,edges,source,target,k)print(result)C完整代码如下#includeiostream#includevector#includequeue#includelimits.h#includealgorithmusingnamespacestd;intminimumThreshold(intn,vectorvectorintedges,intsource,inttarget,intk){// 构建邻接表vectorvectorpairint,intgraph(n);intmaxWeight0;for(autoe:edges){intue[0],ve[1],we[2];graph[u].push_back({v,w});graph[v].push_back({u,w});maxWeightmax(maxWeight,w);}// 检查给定 threshold 下是否存在有效路径autocheck[](intthreshold)-bool{vectorintdist(n,INT_MAX);dist[source]0;// ql 模拟栈后进先出处理轻边qr 模拟队列先进先出处理重边vectorpairint,intql;// 栈queuepairint,intqr;// 队列ql.push_back({source,0});while(!ql.empty()||!qr.empty()){pairint,intp;if(!ql.empty()){pql.back();ql.pop_back();// 从栈顶取出}else{pqr.front();qr.pop();// 从队首取出}intxp.first;intdp.second;if(xtarget){returntrue;}if(ddist[x]){continue;// 不是最优距离跳过}for(autoedge:graph[x]){intyedge.first;intwedge.second;intcost(wthreshold)?1:0;intnddcost;if(nddist[y]){dist[y]nd;if(cost0){ql.push_back({y,nd});// 轻边放入栈}elseif(ndk){qr.push({y,nd});// 重边放入队列}}}}returnfalse;};// 二分查找最小的 thresholdintleft0,rightmaxWeight;intansmaxWeight1;// 初始化为不可能的值while(leftright){intmidleft(right-left)/2;if(check(mid)){ansmid;rightmid-1;}else{leftmid1;}}return(ansmaxWeight)?-1:ans;}intmain(){intn6;vectorvectorintedges{{0,1,5},{1,2,3},{3,4,4},{4,5,1},{1,4,2}};intsource0;inttarget3;intk1;intresultminimumThreshold(n,edges,source,target,k);coutresultendl;return0;}