LeetCode 3620. 恢复网络路径Network Recovery Pathways题目描述给定一个包含 n 个节点的有向无环图节点编号为 0 到 n-1。edges[i] [ui, vi, costi] 表示从 ui 到 vi 的单向边恢复代价为 costi。部分节点可能处于离线状态。online[i] true 表示节点 i 在线。节点 0 和 n-1 始终在线。从 0 到 n-1 的合法路径需满足- 路径上所有中间节点都在线- 路径上所有边的恢复代价之和不超过 k定义每条合法路径的 score 为路径上最小边权。返回所有合法路径中 score 的最大值。若不存在合法路径返回 -1。难度 Hard | 评分 1998 | 来源 Biweekly Contest 161 Q3---解题思路二分答案 Dijkstra核心观察- 路径的 score 路径上的最小边权。我们要最大化这个最小值。- 假设我们猜测一个最小边权 mid如果只保留 cost mid 的边然后判断是否存在从 0 到 n-1 且总代价 k 的路径。- mid 越大可用的边越少可行性越差具有单调性因此可以二分答案。check(mid) 的实现- 在只保留 cost mid 的边的子图上求 0 到 n-1 的最短路径。- 由于边权非负使用堆优化 Dijkstra。- 若最短路 k则 mid 可行。时间复杂度 O((n m) · log n · log W)其中 W 为最大边权。---Java 实现javaimport java.util.*;class Solution {int n;Listint[][] g;long k;// 检查只使用 cost mid 的边是否存在从 0 到 n-1 且总代价 k 的路径boolean check(int mid) {long[] dist new long[n];Arrays.fill(dist, Long.MAX_VALUE / 4);dist[0] 0;PriorityQueuelong[] pq new PriorityQueue(Comparator.comparingLong(a - a[0]));pq.offer(new long[] {0, 0}); // {distance, node}while (!pq.isEmpty()) {long[] cur pq.poll();long d cur[0];int u (int) cur[1];if (d k) return false; // 当前距离已超过 k剪枝if (u n - 1) return true; // 到达终点if (dist[u] d) continue; // 已找到更优路径for (int[] e : g[u]) {int v e[0], w e[1];if (w mid) continue; // 边权不足 mid跳过long nd d w;if (nd dist[v]) {dist[v] nd;pq.offer(new long[] {nd, v});}}}return false;}public int findMaxPathScore(int[][] edges, boolean[] online, long k) {this.k k;n online.length;g new ArrayList[n];for (int i 0; i n; i) g[i] new ArrayList();int l Integer.MAX_VALUE; // 最小边权int r 0; // 最大边权// 建图跳过与离线节点相连的边for (int[] e : edges) {int u e[0], v e[1], w e[2];if (!online[u] || !online[v]) continue;g[u].add(new int[] {v, w});l Math.min(l, w);r Math.max(r, w);}// 二分查找最大可行 scorewhile (l r) {int mid (l r 1) 1;if (check(mid))l mid;elser mid - 1;}return check(l) ? l : -1;}}---代码要点要点 说明离线节点过滤 建图时直接跳过 !online[u] 或 !online[v] 的边避免后续判断二分边界 l 取最小边权r 取最大边权注意使用 (l r 1) 1 避免死循环Dijkstra 剪枝 if (d k) return false 提前终止减少无效搜索最终校验 二分结束后仍需 check(l)因为可能不存在任何合法路径如需其他语言版本Python/C/Go或更详细的复杂度分析可以继续问我。