洛谷1948 电话线Telephone Lines

题意

求 从$1$ 到 $N$ 的一条路径，使得第 $K+1$ 长的边权尽可能小。

其中点数 $N\le 1000$ ，边数 $P\le 2000$，权值 $L_i\le 10^{6}$

题解

直接求肯定没有办法，所以考虑二分答案。

对第 $K+1$ 长的边权 $x$ 进行二分，每次检验就跑一次 $Dijkstra$ ，只是把边权变为 $>x$ 的边的条数，这样就可以得到$>x$ 的边最少的路径 $dis[n]$ 。如果 $dis[n]\le k$ 就满足条件，否则调整二分下界。

#include<bits/stdc++.h>
#define ll long long
#define pr pair<ll,ll>
#define mp make_pair

using namespace std;

inline ll read()
{
    char ch=getchar();
    ll f=1,x=0;
    while (ch<'0' || ch>'9')
    {
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0' && ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return f*x;
}

struct Edge {
    ll next,to,w;
} edge[20005];
ll cnt,head[10005],n,m,k,a,b,c,dis[10005];
bool vis[10005],flag;

inline void add(ll u,ll v,ll w)
{
    edge[++cnt].to=v;
    edge[cnt].w=w;
    edge[cnt].next=head[u];
    head[u]=cnt;
}

inline bool dijkstra(ll mx)
{
    memset(vis,0,sizeof(vis));
    memset(dis,0x3f,sizeof(dis));
    dis[1]=0;
    priority_queue <pr,vector<pr>,greater<pr> > q;
    q.push(mp(0,1));
    while (!q.empty())
    {
        ll x=q.top().second; q.pop();
        if (vis[x]) continue;
        vis[x]=1;
        for (ll i=head[x];i;i=edge[i].next)
        {
            ll y=edge[i].to,w=edge[i].w,now;
            if (w>mx) now=dis[x]+1;
            else now=dis[x];
            if (now<dis[y])
            {
                dis[y]=now;
                q.push(mp(dis[y],y));
            }
        }
    }
    if (dis[n]>=0x3f3f3f3f) flag=1;
    return dis[n]<=k;
}

int main()
{
    n=read(); m=read(); k=read();
    for (ll i=1;i<=m;i++)
    {
        a=read(); b=read(); c=read();
        add(a,b,c);
        add(b,a,c);
    }
    ll l=0,r=1000000,ans;
    while (l<=r)
    {
        ll mid=(l+r)>>1;
        if (dijkstra(mid)) ans=mid,r=mid-1;
        else l=mid+1;
    }
    if (flag) printf("-1");
    else printf("%lld",ans);
    return 0;
}