题解|《算法竞赛进阶指南》Telephone Lines

题面描述：

在某地有n座通信基站，p条双向电缆，第i条连接ai和bi。其中1号基站是总站，现有人希望通讯公司可以对电缆进行升级以期更好地使用，其中对第i条升级需要支付wi。

而电缆公司正在搞活动，某人可以指定一条从1号基站到n号基站的路径，并指定路径上不超过k条电缆，通讯公司可免费进行升级，而收取的费用也仅仅为升级该路径上剩下电缆中最贵的所需花费即可。

问至少要多少钱能完成升级？

简单来说，就是求一条从1到n的最短路，使得路径上第k+1大的边权最小

思路：

我们可以通过二分查找出第k+1条边的边权，边界值l为0，r为1000000.
至于内部如何处理，我们可以将边权小于mid的边的边权看做为0，大于的看做为1，然后跑一边最短路，跑出n点的最短路长度，如果大于k，说明mid小了，所以l=mid+1; ，如果小于k，说明mid大了，所以r=mid;

我用的最短路算法为优先队列优化的dij，再加上O（logn）的二分查找，总的时间复杂度为

my code

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

const int MAXN = 1000010;
const int MAXM = 2000010;

struct node{
    int w,now;
    inline bool operator < (node x)const{
        return w>x.w;
    }
};

int n,m,k;
priority_queue <node> q;

struct Edge{
    int u,v,w,nxt;
}e[MAXM<<1];

int head[MAXN],vis[MAXN],cnt,e_w[MAXM<<1],dist[MAXN];

void add_edge(int u,int v,int w){
    e[++cnt].v=v;
    e[cnt].w=w;
    e[cnt].nxt=head[u];
    head[u]=cnt;
}

void dij(){
    memset(dist,0x3f,sizeof(dist));
    q.push((node){0,1}); dist[1] = 0;
    while(!q.empty()){
        node x=q.top();
        q.pop();
        int u=x.now;
        if(dist[u]<x.w)continue;
        for(int i=head[u];i;i=e[i].nxt){
            int v=e[i].v,w=e_w[i];
            if(dist[v]>dist[u]+w){
                dist[v]=dist[u]+w;
                q.push((node){dist[v],v});
            }
        }
    }
}

void change(int len){
    for(int i=1;i<=cnt;i++){
        if(e[i].w<=len)e_w[i]=0;
        else e_w[i]=1;
    }
    dij();
}

bool can_use(){
    if(dist[n]>k)return 0;
    else return 1;
}

signed main(){
     cin >> n >> m >> k;
    for(int i=1;i<=m;i++){
        int u,v,w;
           cin >> u >> v >> w;
        add_edge(u,v,w);
        add_edge(v,u,w);
    }
    int l=0,r=(int)1e9;
    while(l<r){
        int mid=(l+r)>>1;
        change(mid);
        if(can_use()){
            r=mid;
        }
        else{
            l=mid+1;
        }
    }
    if(l==1e9)cout<<-1<<endl;
    else cout<<l<<endl;
    return 0;
}