acwing340. 通信线路

题目

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

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

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

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

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

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

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

题解

题目要求找到从1到n的k条路径的最短路，然后支付第k+1条路径的最小花费值。
那么只需要这条最短路由k条最小的路径组成即可，然后支付第k+1小的lu路径花费即可。
要寻找第k+1小的值，我们可以通过二分列举这个第k大的值，将比这个值小的路径权值置为0，比这个大的置为1，之后我们将dist[n]的权值与k相比。如果dist[n]<=k说明找到了不超过k条的最短路，否则就没有找到。

关于列举取值范围为什么是0~1e6+1：
如果到dist[n]=k,那么此时只需要支付0.
题中的最大花费是1e6，如果列举到1e6，不分辨是找到最大的花费还是没有找到，所以要比最大值大1.

#include<iostream>
#include<deque>
#include<cstring>
using namespace std;
const int N=1010,M=20010,inf=0x3f3f3f3f;
int dist[N];
int h[N],w[M],e[M],ne[M],idx;
int n,p,k;
bool st[N];
deque<int>q;
void add(int a,int b,int c){
    w[idx]=c;
    e[idx]=b;
    ne[idx]=h[a];
    h[a]=idx++;
}
bool check(int bound){
    memset(dist,0x3f,sizeof dist);
    memset(st,0,sizeof st);
    dist[1]=0;
    q.push_back(1);
    while(q.size()){
        auto t=q.front();
        q.pop_front();
        if(st[t])continue;
        st[t]=true;
        for(int i=h[t];i!=-1;i=ne[i]){
            int j=e[i],x=w[i]>bound;;
            if(dist[j]>dist[t]+x){
                dist[j]=dist[t]+x;
                if(x)q.push_back(j);
                else q.push_front(j);
            }
        }
    }
    return dist[n]<=k;
}
int main(){
    cin>>n>>p>>k;
    memset(h,-1,sizeof h);
    for(int i=0;i<p;i++){
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c);
        add(b,a,c);
    }
    int l=0,r=1e6+1;
    while(l<r){
        int mid=l+r>>1;
        if(check(mid))r= mid;
        else l=mid+1;
    }
    if(r==1e6+1)cout<<-1<<endl;
    else cout<<r<<endl;
    return 0;
    
}