POJ - 3662 Telephone Lines（双端队列+二分）

POJ - 3662 Telephone Lines

题目描述
到$n$有$k$条边可以免费升级，因此只需要求$1$~$N$的所有路径中第$k$ + $1$大的值的最小值，是最大最小值模型，因此可以使用二分求解

对于区间$[0,1000001]$中的某一个点$x$：

• 1. $check(x)$函数表示$:$从$1$走到$N$，最少经过的长度大于$x$的边数的数量是否小于等于$k$，若是则返回$true$，否则返回$false$
• 2. 求出从$1$到$N$最少经过几条长度大于$x$的边可以分类成：
  • 如果边大于$x$，则边权看成$1$
  • 如果边长小于等于$x$，则边权看成$0$

#include<iostream>
#include<cstring>
#include<deque>
using namespace std;
const int N = 1010, M = 20010;int n,m,k;
int h[N],e[M],w[M],ne[M],idx;
int dist[N];
bool st[N];void add(int a,int b,int c)
{
    e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}bool check(int bound)
{
    memset(dist,0x3f,sizeof dist);memset(st,0,sizeof st);deque<int> q;q.push_back(1);dist[1]=0;while(q.size()){
    int t=q.front();q.pop_front();if(st[t]) continue;st[t]=true;for(int i=h[t];~i;i=ne[i]){
    int j=e[i],x=w[i]>bound;if(dist[j]>dist[t]+x){
    dist[j]=dist[t]+x;if(!x) q.push_front(j);else q.push_back(j);}}}return dist[n]<=k;
}int main()
{
    cin>>n>>m>>k;memset(h,-1,sizeof h);while(m--){
    int a,b,c;cin>>a>>b>>c;add(a,b,c);add(b,a,c);}int l=0,r=1e6+1;while(l<r){
    int mid=(l+r)>>1;if(check(mid)) r=mid;else l=mid+1; }if(r==1e6+1) cout<<"-1"<<endl;else cout<<r<<endl;return 0;
}