这篇文章上次修改于 249 天前，可能其部分内容已经发生变化，如有疑问可询问作者。

本文共 1535 个字，阅读时长 ≈ 4 分钟

P1948 [USACO08JAN] Telephone Lines S

题目链接

题意

一个 N 个点 M 条边的无向图，求从1到n的第 k+1 大的边最小

思路

看到要求第 x 大的最小等字眼，容易想到二分答案。二分一下要求的这条边的长度，这里最重要的就是对于题目所给的图的转化，我们在二分出长度之后，将大于这个长度的边的边权看做1，小于等于的看做0，其实就是看这条边需不需要使用免费的次数，然后跑最短路，如果最短路 $\gt k$ 则二分的这条边过小，需要增大，反之则需要减小，找到最小可能的边即可。边权为1最短路可以直接用bfs。但是我用dij 还有就是记得开 long long。

代码

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<queue>
#include<climits>
using namespace std;
int read(){
    int x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        x=(x<<3)+(x<<1)+(c^48);
        c=getchar();
    }
    return x*f;
}
const int N=1003,M=20004;
const long long inf=LONG_LONG_MAX>>2ll;
int n,m,k,ma;
int idx=1,head[N],to[M],nxt[M],w[M];
long long dis[N];
typedef pair<long long,int> pli;
bool vis[N];
void addedge(int u,int v,int _w){
    to[++idx]=v;
    w[idx]=_w;
    nxt[idx]=head[u];
    head[u]=idx;
}
priority_queue<pli> q;
bool operator <(pli a,pli b){
    return b.first<a.first;
}
bool dij(long long x){
    for(int i=0;i<=n;++i) dis[i]=inf,vis[i]=0;
    dis[1]=0ll;
    int u=0,v;
    for(int i=1;i<=n;++i){
        long long mi=inf;
        for(int j=1;j<=n;++j){
            if(!vis[j]&&dis[j]<mi){
                mi=dis[j];
                u=j;
            }
        }
        vis[u]=1;
        for(int j=head[u];j;j=nxt[j]){
            v=to[j];
            //根据二分出来的更改边权
            if(w[j]>x) dis[v]=min(dis[v],dis[u]+1ll);
            else dis[v]=min(dis[v],dis[u]);
        }
    }
    if(dis[n]==inf){
        printf("-1\n");
        exit(0);
    }
    if(dis[n]>k) return 0;
    return 1;
}
void erfen(){
    //二分答案
    int l=0,r=ma,mid,ans=1145141919;
    while(l<=r){
        mid=(l+r)>>1;
        if(dij(mid)) r=mid-1,ans=min(ans,mid);
        else l=mid+1;
    }
    printf("%d\n",ans);
}
int main()
{
    n=read();
    m=read();
    k=read();
    int u,v,_w;
    for(int i=0;i<m;++i){
        u=read(); v=read();
        _w=read(); ma=max(ma,_w);
        addedge(u,v,_w);
        addedge(v,u,_w);
    }
    erfen();
    
    return 0;
}