题目描述

340
二分 最小升级边
看最后 边个数够不够K 这样就找到了 免费有K条 之后最大边会是多少

C++ 代码

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

const int N = 1e3 + 5;
const int M = 1e4 + 5;

int n, m ,k;

int head[N], cnt;
int nxt[M << 1], to[M << 1], d[M << 1];
int dis[N];
bool vis[N];

void ade(int a, int b, int v){
    to[++ cnt] = b;
    nxt[cnt] = head[a];
    d[cnt] = v;
    head[a] = cnt;
}

bool spfa_chk(int limits){
    memset(dis, 0X3f, sizeof dis);
    memset(vis, 0, sizeof vis);
    queue<int> que;
    dis[1] = 0;
    vis[1] = 1;
    que.push(1);
    while(!que.empty()){
        int u = que.front(); que.pop();
        vis[u] = 0;
        for(int i = head[u]; i; i = nxt[i]){
            int v = to[i], z = d[i] >= limits ? 1 : 0 ;
            if(dis[v] > z + dis[u]) {
                dis[v] = z + dis[u];
                if(!vis[v]) que.push(v), vis[v] = 1;
            }
        }
    }
    return dis[n] > k;
}

int main(){
    cin >> n >> m >> k;
    for(int i = 1, x, y, c; i <= m; i ++) {
        cin >> x >> y >> c;
        ade(x, y, c), ade(y, x, c);
    }

    int l = 0, r = 0x3f3f3f3f;
    while(l < r) {
        int mid = l + r + 1 >> 1;
        if(spfa_chk(mid)) l = mid;
        else r = mid - 1;
    }
    if(l < 1001109567) cout << l << endl;
    else cout << -1 << endl;
    return 0;
}