首页 > itarticle > p1948 [usaco08jan]电话线telephone lines（二分答案+最短路）

p1948 [usaco08jan]电话线telephone lines（二分答案+最短路）

admin 11月 14, 2020 0

思路

考虑题目要求求出最小的第k+1大的边权，想到二分答案

然后二分第k+1大的边权wx

把所有边权<=wx的边权变为0，边权>wx的边权变为0，找出最短路之后，如果dis[T]<=k，则答案可行，反之则不可行

似乎有dp解法的样子，真神奇

代码


#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
int dis[1100],u[11000<<1],v[11000<<1],w[11000<<1],n,p,k,fir[11000<<1],nxt[11000<<1],cnt;
void (int ui,int vi,int wi){
    ++cnt;
    u[cnt]=ui;
    v[cnt]=vi;
    w[cnt]=wi;
    nxt[cnt]=fir[ui];
    fir[ui]=cnt;
}
bool check(int mid){
    memset(dis,0x3f,sizeof(dis));
    deque<int> q;
    q.push_back(1);
    dis[1]=0;
    while(!q.empty()){
        int x=q.front();
        q.pop_front();
        for(int i=fir[x];i;i=nxt[i]){
            if(dis[x]+(w[i]>mid)<dis[v[i]]){
                dis[v[i]]=dis[x]+(w[i]>mid);
                if(w[i]>mid)
                    q.push_back(v[i]);
                else
                    q.push_front(v[i]);
            }
        }
    }
    return dis[n]<=k;
}
int main(){
    scanf("%d %d %d",&n,&p,&k);
    for(int i=1;i<=p;i++){
        int a,b,c;
        scanf("%d %d %d",&a,&b,&c);
        addedge(a,b,c);
        addedge(b,a,c);
    }
    int l=0,r=1000100,ans=-1;
    while(l<=r){
        int mid=(l+r)>>1;
        if(check(mid)){
            ans=mid;
            r=mid-1;
        }
        else
            l=mid+1;
    }
    printf("%d",ans);
    return 0;
}