• 题意

    求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;
    }
    /*
    二分边的长度 
    */