思路与算法

二分最终付费上界X。把长度大于X的边赋代价1，其余赋0；0-1 BFS求1到N最少需要免费处理几条超限边，若不超过K则X可行。先判是否连通，再二分最小可行值。

正确性说明

支付上界不超过X等价于所有长于X的选中边都被免单，亦即路径中这种边数≤K。0-1最短路准确给出所需最少免单数。增大X只会减少代价1的边，可行性单调，二分找到最小支付上界。

复杂度

每次判定初始化与0-1 BFS O(N+P)，二分O(log(maxW+1))次；总O((N+P)log(maxW+1))，空间O(N+P)。

易错点

最多走K条边时可以全部免单，答案0。不可达输出-1，N=1输出0。不可把边权和最短路与瓶颈目标混淆。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m, K;
    cin >> n >> m >> K;
    vector<vector<pair<int, int>>> a(n);
    int high = 0;
    for (int i = 0, u, v, w; i < m; i++) {
        cin >> u >> v >> w;
        --u;
        --v;
        a[u].push_back({v, w});
        a[v].push_back({u, w});
        high = max(high, w);
    }
    auto check = [&](int limit) {
        vector<int> d(n, INT_MAX);
        deque<int> q;
        d[0] = 0;
        q.push_back(0);
        while (!q.empty()) {
            int u = q.front();
            q.pop_front();
            for (auto e : a[u]) {
                int z = e.second > limit;
                if (d[e.first] > d[u] + z) {
                    d[e.first] = d[u] + z;
                    if (z)
                        q.push_back(e.first);
                    else
                        q.push_front(e.first);
                }
            }
        }
        return d[n - 1] <= K;
    };
    if (!check(high)) {
        cout << -1 << '\n';
        return 0;
    }
    int low = 0;
    while (low < high) {
        int middle = low + (high - low) / 2;
        if (check(middle))
            high = middle;
        else
            low = middle + 1;
    }
    cout << low << '\n';
}