Telephone Lines

题意

求1到n的所有路中的最小的第k+1长的路。

分析

题目中说，可指定免费修k条路，而最终的费用就取决于边权值第k+1大的边。所以可以二分其值，每次二分出一个mid，跑spfa，求出到n最少要免费牵多少根线。如果小于等于k条，说明这条边还可以更小。

代码

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#include<queue>
#define RG register
#define ll long long
#define INF 0x3f3f3f3f
using namespace std;
const int N=1e3+10,M=1e4+10;
int n,p,k,cnt;
int dis[N],head[N];
bool vis[N];
struct nkl
{
int to,nex,pri;
}e[M<<1];
inline void add(int x,int y,int z)
{
e[++cnt].nex=head[x];
head[x]=cnt;
e[cnt].pri=z;
e[cnt].to=y;
}
inline bool check(int mid)
{
queue<int>q;
memset(dis,0x3f,sizeof(dis));

dis[1]=0;vis[1]=1;
q.push(1);
while(!q.empty())
{
    int s;
    int k=q.front();q.pop();
    for (int i=head[k];i;i=e[i].nex)
    {
        int v=e[i].to;
        if(e[i].pri>mid) s=dis[k]+1;
        else s=dis[k];
        if(s<dis[v])
        {
            dis[v]=s;
            if(!vis[v])
            {
                vis[v]=1;
                q.push(v);
            }
        }
    }
    vis[k]=0;
}

if(dis[n]<=k) return true;
return false;
}
int main()
{
scanf("%d%d%d",&n,&p,&k);
while(p--)
{
    int x,y,z;
    scanf("%d%d%d",&x,&y,&z);
    add(x,y,z),add(y,x,z);
}
int l=0,r=1e6,mid,ans=-1;
while(l<=r)
{
    mid=(l+r)>>1;
    if(check(mid)) r=mid-1,ans=mid;
    else l=mid+1;
}
printf("%d\n",ans);
return 0;
}
/*
二分边的长度 
*/