LeetCode 3620. 恢复网络路径 Rust 实现rustuse std::collections::BinaryHeap;use std::cmp::Reverse;impl Solution {pub fn find_max_path_score(edges: VecVeci32, online: Vecbool, k: i64) - i32 {let n online.len();let mut g: VecVec(usize, i32) vec![vec![]; n];let mut l i32::MAX;let mut r 0i32;// 建图过滤与离线节点相连的边for e in edges {let u e[0] as usize;let v e[1] as usize;let w e[2];if !online[u] || !online[v] {continue;}g[u].push((v, w));l l.min(w);r r.max(w);}// 没有有效边if l i32::MAX {return -1;}// 检查只使用 cost mid 的边能否在总代价 k 内从 0 到达 n-1let check |mid: i32| - bool {let mut dist vec![i64::MAX / 4; n];dist[0] 0;// Rust 的 BinaryHeap 是最大堆用 Reverse 包装得到最小堆let mut pq BinaryHeap::new();pq.push(Reverse((0i64, 0usize))); // (distance, node)while let Some(Reverse((d, u))) pq.pop() {if d k {return false; // 剪枝已超过 k}if u n - 1 {return true; // 到达终点}if dist[u] d {continue; // 已有更优路径}for (v, w) in g[u] {if w mid {continue; // 边权不足 mid跳过}let nd d w as i64;if nd dist[v] {dist[v] nd;pq.push(Reverse((nd, v)));}}}false};// 二分查找最大可行的最小边权while l r {let mid (l r 1) 1;if check(mid) {l mid;} else {r mid - 1;}}if check(l) { l } else { -1 }}}---Rust 实现要点要点 说明Reverse BinaryHeap Rust 标准库的优先队列默认是最大堆用 Reverse 包装元组得到最小堆实现 Dijkstra类型转换 边权 w 为 i32累加和 dist 为 i64通过 w as i64 安全转换w ≤ 10⁹防溢出初始化 dist 初始化为 i64::MAX / 4避免加法溢出闭包捕获 check 闭包捕获 g、n、k无需额外传参边界处理 若所有边均连接离线节点l 保持 i32::MAX直接返回 -1时间复杂度 O((n m) · log n · log W)空间复杂度 O(n m)
