LeetCode 3620. 恢复网络路径 C 实现cpp#include bits/stdc.husing namespace std;class Solution {public:int findMaxPathScore(vectorvectorint edges, vectorbool online, long long k) {int n online.size();vectorvectorpairint, int g(n);int l INT_MAX, r 0;// 建图过滤与离线节点相连的边for (auto e : edges) {int u e[0], v e[1], w e[2];if (!online[u] || !online[v]) continue;g[u].push_back({v, w});l min(l, w);r max(r, w);}// 没有有效边if (l INT_MAX) return -1;// 检查只使用 cost mid 的边能否在总代价 k 内从 0 到达 n-1auto check [](int mid) - bool {const long long INF LLONG_MAX / 4;vectorlong long dist(n, INF);dist[0] 0;// 小根堆{distance, node}using P pairlong long, int;priority_queueP, vectorP, greaterP pq;pq.push({0, 0});while (!pq.empty()) {auto [d, u] pq.top();pq.pop();if (d k) return false; // 剪枝已超过 kif (u n - 1) return true; // 到达终点if (dist[u] d) continue; // 已有更优路径for (auto [v, w] : g[u]) {if (w mid) continue; // 边权不足 mid跳过long long nd d w;if (nd dist[v]) {dist[v] nd;pq.push({nd, v});}}}return false;};// 二分查找最大可行的最小边权while (l r) {int mid (l r 1) 1;if (check(mid))l mid;elser mid - 1;}return check(l) ? l : -1;}};---C 实现要点要点 说明greaterP 小根堆 priority_queue 默认大根堆用 greater 实现 Dijkstra 所需的小根堆结构化绑定 auto [d, u] C17 特性简洁地解包 pair代码更直观防溢出 dist 使用 long long初始化为 LLONG_MAX / 4 避免加法溢出类型推导 using P ... 简化 priority_queue 模板参数书写边界处理 若所有边均连接离线节点l 保持 INT_MAX直接返回 -1时间复杂度 O((n m) · log n · log W)空间复杂度 O(n m)