题目描述

这题的思路太妙了，二分找一个值x，x为路径的长度，
算法不再于求最短路径，而是直接求满足check的x的值
check的限制为dist[n]<=k

注意check的返回值为，dist[n]<=k时返回1， 当w[i]>x 时v为1

可以这么理解，当x很小的时候，好多边的边权都为1，这样肯定不满足dist[n]<=k，所以要慢慢放大x

#include <iostream>
#include <cstring>
#include <deque>

using namespace std;

int n,m,k;

const int N=10010;
int h[1010],e[20010],ne[20010],st[20010],w[20010],idx;
int dist[1010];
deque<int> q;
void add(int a,int b,int c)
{
    e[idx]=b;
    ne[idx]=h[a];
    w[idx]=c;
    h[a]=idx++;
}

int check(int x)
{
    memset(dist,0x3f,sizeof dist);
    memset(st,0,sizeof st);
    dist[1]=0;


    q.push_back(1);
    while(q.size())
    {
        auto t=q.front();
        q.pop_front();
        if(st[t]) continue;
        st[t]=1;

        for(int i=h[t];i!=-1;i=ne[i])
        {
            int j=e[i];
            int v=w[i]>x;
            if(dist[j]>dist[t]+v)
            {
                dist[j]=dist[t]+v;

                if(v==0)
                q.push_front(j);
                else
                q.push_back(j);

            }
        }
    }

    return dist[n]<=k;
}

int main()
{
    cin>>n>>m>>k;
    memset(h,-1,sizeof h);
    for(int i=1;i<=m;i++)
    {
        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;
            //cout<<"aa"<<endl;
        }
        else
        l=mid+1;

    }
    if(r==1e6+1) r=-1;
    cout<<r;

    return 0;
}

二刷，重点是二分

    二分一定要明确找的是什么，我们要找的是满足dist[n]<=k的最大的dist[n]
    mid再小1，mid就会等于一条边的长度，然后再加一条边，使dist[n]大1
    因此mid越小，dist[n]越大，因此找最小的mid
    因此即使等于了，仍让r继续左移，继续找小的

考虑一种极端情况，所有w[i]=100
这样因为v=w[i]>x，当x=101时，check成功
当x=99时，check失败
当x=100时，check成功
因此找的是最小的，满足check的值
所以最终求得的mid值，一定等于临界的那条边的权重，比他再小，check就失败了

双端队列的本质是djk，要st数组的使用方式和djk一样，出队时判重

#include <iostream>
#include <cstring>
#include <deque>

using namespace std;

const int N=10010,M=20010;


int h[N],e[M],ne[M],w[M],idx,st[N],dist[N];
int n,m,k;


void add(int a,int b,int c)
{
    e[idx]=b;
    ne[idx]=h[a];
    w[idx]=c;
    h[a]=idx++;
}

int check(int x)
{
    memset(dist,0x3f,sizeof dist);
    memset(st,0,sizeof st);
    deque<int> q;
    dist[1]=0;
    q.push_back(1);
    while(q.size())
    {
        int t=q.front();
        q.pop_front();
        if(st[t]) continue;
        st[t]=1;
        for(int i=h[t];i!=-1;i=ne[i])
        {
            int j=e[i];
            int v=w[i]>x;
            if(dist[j]>dist[t]+v)
            {
                dist[j]=dist[t]+v;
                if(v==0)
                {
                    q.push_front(j);
                }
                else q.push_back(j);
            }

        }

    }


    return dist[n]<=k;
}


int main()
{
    cin>>n>>m>>k;
    memset(h,-1,sizeof h);
    for(int i=1;i<=m;i++)
    {
        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;
        //二分一定要明确找的是什么，我们要找的是满足dist[n]<=k的最大的dist[n]
        //mid再小1，mid就会等于一条边的长度，然后再加一条边，使dist[n]大1
        //因此mid越小，dist[n]越大，因此找最小的mid
        // 因此即使等于了，仍让r继续左移，继续找小的
        if(check(mid)) r=mid;
        else l=mid+1;
    }
    if(r==1e6+1) r=-1;

    cout<<r;
    return 0;
}

当然，若check里返回值为 return dist[n]>k;

    while(l<r)
    {
        int mid=l+r>>1;
        if(check(mid)) l=mid+1;
        else r=mid;
    }

check为1就说明失败了，要放大mid。这时候就是体现二分思想的时候了
如99 100 101， 99是失败，101和100是成功，我们要找的是最小的成功的值，即临界值100
若mid=101时,进入else，r=mid要缩小
若mid=99，进入l=mid+1，则要放大
成功的100，是不会进入l=mid+1 里的，因此可以放心的等着r靠近过来

像本题的第一种写法，如果mid是成功的，则直接把r移到mid，不动了，等着l
但本题的第二种写法，如果mid是失败的，则把l移到mid+1的位置，希望mid+1位置的可以成功

四刷，磕磕绊绊的写出来了

二分掌握过关
有几个小坑注意一下：
1. 因为二分里要多次check，做多次djk，因此要在djk里面初始化

#include <iostream>
#include <cstring>
#include <queue>
#include <vector>

using namespace std;

const int N=1001000;
int n,m,k;
int a[10];
int e[N],ne[N],h[N],w[N],idx,st[N];
int dist[N];

typedef pair<int,int> pii;


void add(int a,int b,int c)
{
    e[idx]=b;
    ne[idx]=h[a];
    w[idx]=c;
    h[a]=idx++;
}

int check(int p)
{
    priority_queue<pii,vector<pii>,greater<pii>> heap;
    memset(dist,0x3f,sizeof dist);
    memset(st,0,sizeof st);
    dist[1]=0;
    heap.push({0,1});
    while(heap.size())
    {
        auto t=heap.top();
        heap.pop();
        int u=t.second;
        int d=t.first;

        if(st[u]) continue;
        st[u]=1;
        for(int i=h[u];i!=-1;i=ne[i])
        {
            int j=e[i];
            int ww=(w[i]>p);
            //cout<<w[i]<<endl;
            if(dist[j]>dist[u]+ww)
            {
                dist[j]=dist[u]+ww;
                heap.push({dist[j],j});
            }
        }
    }
    //cout<<dist[n]<<endl;
    if(dist[n]>k) return 0;
    else return 1;

}

int main()
{
    cin>>n>>m>>k;
    memset(h,-1,sizeof h);

    for(int i=1;i<=m;i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c);
        add(b,a,c);

    }

    //二分找最小的p，使得djk成立
    int l=0;
    int r=1e6+7;
    while(l<r)
    {
        int mid=l+r>>1;

        if(check(mid)) r=mid;
        else l=mid+1;
    }
    if(r>1e6) cout<<-1;
    else
    cout<<r;
    return 0;
}

2023/12/3

复习了二分，复习了双端队列优化的djk(用于只有01两种边权的)
重点：

将问题转化成：只有01两种边权的djk，因此用双端队列优化

• 0代表低于阈值x，不用算的电路
• 1代表超过阈值x，需要花费一次免费升级机会的电路，总数要与k作比较

二分的目标: 找到最小的x，满足升级的次数(小于)等于k
转化成: x越小,dist[n]就会越大，因此要逐渐放大x，找到满足dist[n]<=k的最小的x
转化成: 满足足dist[n]==k的有很多x, 找这里面x最小的，也就是排在最左边的
转化成: 1 1 2 2 3 3，类似这种序列中，找2的起始位置，也就是mid右边的数都>=2

二分的代码：
check成功代表: 当前最小花费已经小于等于k了，试试x能不能继续缩小

    while(l<r)
    {
        int mid=l+r>>1;
        if(check(mid))
        {
            r=mid;
        }
        else
        {
            l=mid+1;
        }
    }

#include <iostream>
#include <cstring>
#include <deque>

using namespace std;


const int N=20010,M=20010;
int e[N],w[N],ne[N],h[N];
int idx;
int n,m,k;
int dist[N], st[N];


void add(int a, int b, int c)
{
    e[idx] = b;
    ne[idx] = h[a];
    w[idx] = c;
    h[a] = idx++;
}


int check(int x)
{
    memset(dist, 0x3f, sizeof(dist));
    memset(st, 0, sizeof(st));

    deque<int> q;

    q.push_front(1);
    dist[1] = 0;

    // 这里的djk，只有0和1两种边权
    // 0代表低于阈值x，不用算的电路
    // 1代表超过阈值x，需要花费一次免费升级机会的电路，总数要与k作比较
    while(q.size())
    {
        int t=q.front();
        q.pop_front();

        if(st[t]) continue;
        st[t] = 1;

        for(int i=h[t];i!=-1;i=ne[i])
        {
            int j=e[i];
            // 如果当前路的权重大于阈值x，则需要消耗一次免费升级的机会
            int weight = w[i]>x;

            if(dist[j] > dist[t]+weight)
            {
                dist[j] = dist[t]+weight;
                if(weight == 0)
                {
                    q.push_front(j);
                }
                else
                {
                    q.push_back(j);
                }
            }
        }
    }

    // 二分的目标: 找到最小的x，满足升级的次数(小于)等于k
    // 转化成: x越小,dist[n]就会越大，因此要逐渐放大x，找到满足dist[n]<=k的最小的x
    // 转化成: 满足足dist[n]==k的有很多x, 找这里面x最小的，也就是排在最左边的
    // 转化成: 1 1 2 2 3 3，类似这种序列中，找2的起始位置，也就是mid右边的数都>=2
    return dist[n]<=k;

}

int main()
{
    memset(h, -1, sizeof(h));
    cin>>n>>m>>k;

    for(int i=1;i<=m;i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c);
        add(b,a,c);
    }

    // 找最小的费用mid，使得mid可以满足免费升级的电缆数不超过k
    int l=0;
    int r=1e6+1;

    while(l<r)
    {
        int mid=l+r>>1;

        // check成功代表: 当前最小花费已经小于等于k了，试试x能不能继续缩小
        if(check(mid))
        {
            r=mid;
        }
        else
        {
            l=mid+1;
        }
    }

    if(r==1e6+1) r=-1;

    cout<<r;


    return 0;
}