架设电话线

一本通·提高篇 · 代码 · cpp · 难度 4/5 · 共 1905 字
二分答案配合双端队列0-1 BFS
一本通
例
正文

// 原题：https://oj.yecheng.tv/p/T1496
// 题意：无向图上求一条 1 到 N 的路径，使路径上第 K+1 大的边权尽量小（可免费免去 K 条），不可达输出 -1。
// 思路：二分答案 x，把边权大于 x 的边记代价 1、其余记 0，用双端队列做 0-1 BFS 求最小代价，代价不超过 K 即说明 x 可行。
// 复杂度：O((N+P) log L) 时间 / O(N+P) 空间
// 易错点：先单独判断 1 到 N 是否连通，不连通必须输出 -1 而不是二分上界；二分下界从 0 开始，因为答案可能是 0。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1005;
const int INF = 0x3f3f3f3f;
struct Edge{
    int to, w;
};
vector<Edge> adj[MAXN];
int n, k;
int dista[MAXN];
bool reach(){
    queue<int> q;
    vector<bool> vis(n + 1, false);
    vis[1] = true;
    q.push(1);
    while(!q.empty()){
        int u = q.front();
        q.pop();
        for(size_t i = 0; i < adj[u].size(); i++){
            int v = adj[u][i].to;
            if(!vis[v]){
                vis[v] = true;
                q.push(v);
            }
        }
    }
    return vis[n];
}
bool check(int x){
    deque<int> dq;
    for(int i = 1; i <= n; i++) dista[i] = INF;
    dista[1] = 0;
    dq.push_back(1);
    while(!dq.empty()){
        int u = dq.front();
        dq.pop_front();
        for(size_t i = 0; i < adj[u].size(); i++){
            int v = adj[u][i].to;
            int c = adj[u][i].w > x ? 1 : 0;
            if(dista[u] + c < dista[v]){
                dista[v] = dista[u] + c;
                if(c) dq.push_back(v);
                else dq.push_front(v);
            }
        }
    }
    return dista[n] <= k;
}
int main(){
    int m;
    if(!(cin >> n >> m >> k)) return 0;
    int maxw = 0;
    for(int i = 0; i < m; i++){
        int a, b, l;
        cin >> a >> b >> l;
        adj[a].push_back({b, l});
        adj[b].push_back({a, l});
        if(l > maxw) maxw = l;
    }
    if(!reach()){
        cout << -1 << '\n';
        return 0;
    }
    int l = 0, r = maxw;
    while(l < r){
        int mid = (l + r) / 2;
        if(check(mid)) r = mid;
        else l = mid + 1;
    }
    cout << l << '\n';
    return 0;
}
架设电话线

正文

一本通·提高篇的其它内容
