Acwing 340 通信电路 ( ఠൠఠ )ﾉ

这道题有三个关键的思路

A. 题意就是找第k + 1 大的值（因为前面k个值是不算的）

那么问题来到怎么去找到第k + 1 大的值 – 二分

B. 二分随机到的数的右边都是比mid要大的数，大于k的话mid要往右移，小于k的话r就要往左移动

那么问题又来了，等于k的时候要怎么样移动，这很关键 – r往左移，知道不满足mid右边的个数为k为止，那么为什么呢 – 因为这样能找到不大于mid，且属于图的边权（这点很关键，这就是为什么代码中并没有判断随机出来的mid是不是属于输入中图的边权，已经隐藏再二分中了）

C. 最后一步就是怎么样去用dijkstra去求 在mid的条件下大于mid的最小数，正常写的话肯定是有问题的，边权确定的话走的路就永远是那一条，比如上图的 1 - 2 - 5 ，不会走 1 - 3 - 2 - 5。 0 / 1 化，将比mid大的数看作1，小于等于的看作0 ，这想法是真🐂

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

const int N = 1E5 + 2;

#define pii pair<int, int>
#define inf 0x3f3f3f3f
int head[N],cnt;
int vis[N],dis[N];
int ans, n, k, p;

struct Edge{
    int to, next, w;
}edges[N];

void add(int from, int to, int w){
    edges[cnt].w = w;
    edges[cnt].to = to;
    edges[cnt].next = head[from];
    head[from] = cnt++;
}

void init(){
    memset(dis, inf, sizeof dis);
    memset(vis, 0, sizeof vis);
    memset(head, -1 , sizeof head);
    cnt = 0;
}

int dijstra(int mid){
    priority_queue<pii, vector<pii>, greater<pii>> q;

    memset(vis, 0, sizeof vis);
    memset(dis, inf, sizeof dis);

    dis[1] = 0; // 每次的起点都是1
    q.push(make_pair(dis[1],1));

    while(!q.empty()){
        int now = q.top().second;
        q.pop();
        if(vis[now])
            continue;
        vis[now] = 1;
        for(int i = head[now]; i != -1; i = edges[i].next){
            int v = edges[i].to;
            int w;
            if(edges[i].w <= mid)
                w = 0;
            else
                w = 1;
            if(dis[v] > dis[now] + w) {
                dis[v] = dis[now] + w;
                q.push(make_pair(dis[v], v));
            }
        }
    }
    return dis[n];
}

int main(){
    init();
    cin >> n >> p >> k;
    for(int i = 0; i < p; i++){
        int a, b , c;
        cin >> a >> b >> c;
        add(a, b, c);
        add(b, a, c);
    }

    if(dijstra(0) == inf){
        cout << -1 << endl;
        return 0;
    }

    int l = 0, r = 1e6;
    int mid;
    while(l <= r){
        mid = (l + r) / 2;
        if(dijstra(mid) <= k){
            ans = mid;
            r = mid - 1;
        }
        else{
            l = mid + 1;
        }

    }

    cout << ans << endl;
    return 0;
}