340-通信线路

在郊区有 N 座通信基站，P 条双向电缆，第 i 条电缆连接基站 Ai 和 Bi。

特别地，1 号基站是通信公司的总站，N 号基站位于一座农场中。

现在，农场主希望对通信线路进行升级，其中升级第 i 条电缆需要花费 Li。

电话公司正在举行优惠活动。

农产主可以指定一条从 1 号基站到 N 号基站的路径，并指定路径上不超过 K 条电缆，由电话公司免费提供升级服务。

农场主只需要支付在该路径上剩余的电缆中，升级价格最贵的那条电缆的花费即可。

求至少用多少钱可以完成升级。

输入格式
第 1 行：三个整数 N，P，K。

第 2..P+1 行：第 i+1 行包含三个整数 Ai,Bi,Li。

输出格式
包含一个整数表示最少花费。

若 1 号基站与 N 号基站之间不存在路径，则输出 −1。

数据范围

0≤K<N≤1000,
1≤P≤10000,
1≤Li≤1000000

输入样例：
5 7 1
1 2 5
3 1 4
2 4 8
3 2 3
5 2 9
3 4 7
4 5 6
输出样例：
4

method: 二分+Dijkstra

我们希望找到1到N的路径中第k+1大的权值的最小值

二分：对答案进行二分，假设我们需要支付mid，则线路中小于mid的就不需要支付，大于mid的希望可以免费，所以小于mid的权值可以看成0，大于mid的权值可以看成1，统计最短路中大于mid的权值个数，如果小于k，那我们可以花得更小一些，让更多的去用免费（贪心的感觉），所以r=mid，如果大于k，那这种情况就不行了，必须花多点，所以l=mid+1

比如k=1，一条线路是[4,5,6]其中大于5的个数为1，需要支付4，另一条是[3,5,6]其中大于5的个数为1，需要支付3
各种mid结果如下

mid:     0 1 2 3 4 5 6 7 8
dist[N]: 2 2 2 2 1 1 1 0 0

答案即为4

所以希望我们支付mid算出来的免费个数是小于等于k的，并且尽可能小

#include <iostream>
#include <algorithm>
#include <queue>
#include <cstring>
using namespace std;

const int N = 1005;
const int M = 10005;

struct edge {
    int v, w, next;
}e[M*2];
int head[N], cnt;
void add(int u, int v, int w) {
    e[++cnt].v = v;
    e[cnt].w = w;
    e[cnt].next = head[u];
    head[u] = cnt;
}
int dist[N];
bool inq[N];

int n, m, k;
int u, v, w;

bool dijkstra(int num) {
    memset(dist, 0x3f, sizeof(dist));
    memset(inq, false, sizeof(inq));
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> q;
    q.push({0, 1});
    dist[1] = 0;
    while (!q.empty()) {
        auto x = q.top();
        q.pop();
        int u = x.second;
        if (inq[u]) continue;
        inq[u] = true;
        for (int i = head[u]; i; i = e[i].next) {
            int v = e[i].v;
            int w = dist[u] + (e[i].w > num ? 1 : 0);
            if (dist[v] > w) {
                dist[v] = w;
                q.push({w, v});
            }
        }
    }
    return dist[n] <= k;
}

int main() {
    cin >> n >> m >> k;
    for (int i = 0; i < m; i++) {
        cin >> u >> v >> w;
        add(u, v, w);
        add(v, u, w);
    }
    int l = 0, r = 1e6+1;   // 权值最大是1e6
    while (l < r) {
        int mid = (l + r) >> 1;
        if (dijkstra(mid)) r = mid;
        else l = mid + 1;
    }
    if (r != 1e6+1) cout << r << endl;
    else cout << -1 << endl;
    return 0;
}