题目地址：

https://leetcode.com/problems/minimum-cost-to-repair-edges-to-traverse-a-graph/description/

给定一个$n$阶无向非负权图，点编号$0$开始，边数为$m$，再给定一个正整数$k$。问最少的$x$使得删掉所有边权大于$x$的边的情况下，从$0$到$n-1$存在一条边数不超过$k$的路径。题目保证$n\ge 2$。

答案一定是所有边权之一，可以用二分 + BFS来做，BFS求最短路看是否小于等于$k$。这里的边权在求最短路里不是作为真的边权来处理，而是只是视为$\infty$或$1$（能走就是$1$，不能就是$\infty$）。代码如下：

class Solution {
public:
  int minCost(int n, vector<vector<int>> &es, int k) {
    int m = es.size();
    vector<int> h(n, -1), e(m << 1), ne(m << 1), w(m << 1);
    int idx = 0;
    auto add = [&](int a, int b, int c) {
      e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
    };
    vector<int> lens;
    lens.reserve(m);
    for (auto &e : es) {
      int a = e[0], b = e[1], c = e[2];
      add(a, b, c), add(b, a, c);
      lens.push_back(c);
    }
    sort(lens.begin(), lens.end());
    lens.erase(unique(lens.begin(), lens.end()), lens.end());
    auto bfs = [&](int maxLen) {
      assert(n >= 2);
      queue<int> q{{0}};
      vector<bool> vis(n);
      vis[0] = true;
      int step = 0;
      while (q.size()) {
        step++;
        if (step > k) return false;
        for (int _ = q.size(); _--; ) {
          int u = q.front(); q.pop();
          for (int i = h[u]; ~i; i = ne[i]) {
            int v = e[i], c = w[i];
            if (c <= maxLen && !vis[v]) {
              if (v == n - 1) return true;
              vis[v] = true;
              q.push(v);
            }
          }
        }
      }
      return false;
    };
    int l = 0, r = lens.size() - 1;
    while (l < r) {
      int mid = l + r >> 1;
      if (bfs(lens[mid])) r = mid;
      else l = mid + 1;
    }
    return bfs(lens[l]) ? lens[l] : -1;
  }
};

时间复杂度$O((n+m)\log m)$，空间$O(n+m)$。