核心思路二分答案 0-1 BFS1. 阈值具有单调性阈值越大权重超过阈值的重边越少越容易满足重边数不超过 k 的限制因此可以二分查找最小可行阈值。2. 可行性校验将轻边权重≤阈值代价记为 0重边代价记为 1用 0-1 BFS 求解起点到终点的最少重边数若 ≤ k 则当前阈值可行。0-1 BFS 时间复杂度为 O(nm)效率优于 Dijkstra。C 完整实现cpp#include vector#include dequeusing namespace std;class Solution {public:int minimumThreshold(int n, vectorvectorint edges, int source, int target, int k) {if (source target) {return 0;}// 构建无向邻接表vectorvectorpairint, int adj(n);int max_weight 0;for (auto e : edges) {int u e[0], v e[1], w e[2];adj[u].emplace_back(v, w);adj[v].emplace_back(u, w);max_weight max(max_weight, w);}int left 0, right max_weight;int ans -1;// 二分查找最小阈值while (left right) {int mid left (right - left) / 2;if (check(adj, source, target, n, mid, k)) {ans mid;right mid - 1; // 尝试更小的阈值} else {left mid 1;}}return ans;}private:// 0-1 BFS校验阈值 threshold 下source 到 target 的最少重边数是否 ≤ kbool check(vectorvectorpairint, int adj, int start, int end, int n, int threshold, int k) {// 最多 n-1 条边用 n 表示不可达避免 INT_MAX 加法溢出vectorint dist(n, n);dist[start] 0;dequeint dq;dq.push_front(start);while (!dq.empty()) {int u dq.front();dq.pop_front();// 第一次到达终点即为最短路径可提前终止if (u end) {break;}for (auto edge : adj[u]) {int v edge.first;int w edge.second;int cost (w threshold) ? 1 : 0;// 松弛操作if (dist[v] dist[u] cost) {dist[v] dist[u] cost;if (cost 0) {dq.push_front(v); // 轻边加入队首同层扩展} else {dq.push_back(v); // 重边加入队尾下层扩展}}}}return dist[end] k;}};复杂度分析- 时间复杂度O((nm)\log W)其中 W 为最大边权。二分执行 \log W 轮每轮 0-1 BFS 耗时 O(nm)。- 空间复杂度O(nm)邻接表 距离数组 双端队列。关键边界处理1. 起点与终点重合无需经过任何边直接返回 02. 图不连通终点不可达最终返回 -13. 避免整数溢出距离数组初始化为节点数 n 路径最多 n-1 条边替代 INT_MAX 防止加法溢出4. 提前终止0-1 BFS 第一次弹出终点时距离即为最小值可直接跳出循环。
