Kimi LeetCode 3620. 恢复网络路径 C++实现

LeetCode 3620. 恢复网络路径 C++ 实现

```cpp
#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
int findMaxPathScore(vector<vector<int>>& edges, vector<bool>& online, long long k) {
int n = online.size();
vector<vector<pair<int, 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-1
auto check = [&](int mid) -> bool {
const long long INF = LLONG_MAX / 4;
vector<long long> dist(n, INF);
dist[0] = 0;

// 小根堆：{distance, node}
using P = pair<long long, int>;
priority_queue<P, vector<P>, greater<P>> pq;
pq.push({0, 0});

while (!pq.empty()) {
auto [d, u] = pq.top();
pq.pop();

if (d > k) return false; // 剪枝：已超过 k
if (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;
else
r = mid - 1;
}

return check(l) ? l : -1;
}
};
```

---

C++ 实现要点

要点 说明
`greater<P>` 小根堆 `priority_queue` 默认大根堆，用 `greater<>` 实现 Dijkstra 所需的小根堆
结构化绑定 `auto [d, u]` C++17 特性，简洁地解包 `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)`