【POJ3662】Telephone Lines

题意

一共有N个电线杆，有P对电线杆是可以连接的，用几条线连接在一起的电线杆之间都可相互通信，现在想要使得电线杆1和电线杆N能相互通信，并且电线公司提出K条电线是可以免费使用的，当使用电线的数量超过K条，超出的电线要收费，收的总费用为去掉免费使用的K条电线之后最长的那条电线的长度。现在需要尽可能的减少费用，问最少费用是多少
一句话题意：在无向图上找出一条从1到N的路径，使得路径上第K+1大的边权尽量小，求出这个边权。

分析

最大值最小，考虑二分答案，转换为判定问题。

类似于运输计划，我们把比答案大的边记为1，比答案小的边记为0，然后跑最短路，如果得到的距离>K说明二分的mid值小了，否则就是大了。

其中，求最短路用双端队列bfs可以将时间复杂度降一个log

代码

#include<deque>  
#include<iostream>  
#include<algorithm>  
#include<cstdio>  
#include<cstring>  
using namespace std;  
#define N 10010  
int n,m,k,l,r,mid,cnt,ans=-1;  
int d[N],vis[N],first[N];  
struct email  
{  
    int u,v,o,w;  
    int nxt;  
}e[N*4];  
inline void add(int u,int v,int o)  
{  
    e[++cnt].nxt=first[u];first[u]=cnt;  
    e[cnt].u=u;e[cnt].v=v;e[cnt].o=o;  
}  
  
inline int check(int x)  
{  
    deque<int>q;  
    for(int i=1;i<=cnt;i++)e[i].w=0;  
    memset(d,0x3f,sizeof(d));  
    memset(vis,0,sizeof(vis));  
    for(int i=1;i<=cnt;i+=2)  
        if(e[i].o>x)e[i].w=1,e[i+1].w=1;  
    q.push_back(1);d[1]=0;vis[1]=1;  
    while(!q.empty())  
    {  
        int u=q.front();q.pop_front();  
        if(u==n)    return d[n]<=k;  
        for(int i=first[u];i;i=e[i].nxt)  
        {  
            int v=e[i].v,w=e[i].w;  
            d[v]=min(d[v],d[u]+w);  
            if(!vis[v])  
                if(!w)q.push_front(v);  
                else q.push_back(v);  
            vis[v]=1;  
        }  
    }  
    return 0;  
}  
  
int main()  
{  
    scanf("%d%d%d",&n,&m,&k);  
    for(int i=1;i<=m;i++)  
    {  
        int u,v,o;  
        scanf("%d%d%d",&u,&v,&o);  
        add(u,v,o);add(v,u,o);r=max(r,o);  
    }  
    while(l<=r)  
    {  
        mid=l+r>>1;  
        if(check(mid))r=mid-1,ans=mid;  
        else l=mid+1;     
    }  
    printf("%d
",ans);  
    return 0;  
}