P8724 [蓝桥杯 2020 省 AB3] 限高杆 题解

· · 题解

题目传送门：P8724 [蓝桥杯 2020 省 AB3] 限高杆

解决方法：

基本思想是分层图，但提供一个与众不同的做法（双倍经验 P1849）。

定义两个队列 q,q_2，其中，q 是跑 Dijkstra 所用的队列，q_2 记录有限高杆的路通向的点和距离（具体实现参考代码）。

邻接表存图，多开一个 D 记录这条路上是否有限高杆。

加点操作：

void add(int a,int b,int c,int d)
{//加点操作
    E[a].push_back(b);
    V[a].push_back(c);
    D[a].push_back(d);
}

在 Dijkstra 开始前，清空 q，把 q_2 中的值附到 q 中，同时更新从起点到 q_2 中的点的最小距离，实现如下：

void copy_queue()
{
    while(!q.empty()) q.pop();
    while(!q2.empty()) q.push(q2.top()),dis[q2.top().second]=min(dis[q2.top().second],q2.top().first),q2.pop();
    //同时更新dis记录的最短路（类似延时更改）
}

Dijkstra 函数中，

void dij(int cnt)
{
    memset(vis,0,sizeof(vis));
    //清空vis数组
    copy_queue();//把 q_2 附给 q

    while(q.size())
    {
        int x=q.top().second;
        q.pop();

        if(vis[x]) continue;//到过这个节点
        vis[x]=1;//记录

        for(int i=0;i<E[x].size();i++)
        {
            int k=E[x][i];
            int w=V[x][i];
            int d=D[x][i];

            if(d) q2.push(make_pair(min(dis[k],dis[x]+w),k));
            //注意把长度取min，否则拆除后最短路无法保证
            else if(dis[k]>dis[x]+w)//松弛操作
            {
                dis[k]=dis[x]+w;
                q.push(make_pair(dis[k],k));
            }
        }
    }
    maxn=max(maxn,dis[n]);//这里是记录没拆限高杆时的最短路
    minn=min(minn,dis[n]);//拆限高杆后的最短路
    if(cnt<2) dij(cnt+1);//没拆够两个限高杆，继续拆。
}

完整代码：

#include<bits/stdc++.h>
#define reg register
#define int long long
using namespace std; 
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >q,q2;

int n,m;
vector<int> E[100005],V[100005];
vector<int> D[100005];
int maxn=-999999999,minn=9999999999;
int dis[1<<20];
bool vis[1<<20];

void copy_queue()
{
    while(!q.empty()) q.pop();
    while(!q2.empty()) q.push(q2.top()),dis[q2.top().second]=min(dis[q2.top().second],q2.top().first),q2.pop();
    //同时更新dis记录的最短路（类似延时更改）
}

void add(int a,int b,int c,int d)
{//加点操作
    E[a].push_back(b);
    V[a].push_back(c);
    D[a].push_back(d);
}

void dij(int cnt)
{
    memset(vis,0,sizeof(vis));
    //清空vis数组
    copy_queue();//把 q_2 附给 q

    while(q.size())
    {
        int x=q.top().second;
        q.pop();

        if(vis[x]) continue;//到过这个节点
        vis[x]=1;//记录

        for(int i=0;i<E[x].size();i++)
        {
            int k=E[x][i];
            int w=V[x][i];
            int d=D[x][i];

            if(d) q2.push(make_pair(min(dis[k],dis[x]+w),k));
            //注意把长度取min，否则拆除后最短路无法保证
            else if(dis[k]>dis[x]+w)//松弛操作
            {
                dis[k]=dis[x]+w;
                q.push(make_pair(dis[k],k));
            }
        }
    }
    maxn=max(maxn,dis[n]);//这里是记录没拆限高杆时的最短路
    minn=min(minn,dis[n]);//拆限高杆后的最短路
    if(cnt<2) dij(cnt+1);//没拆够两个限高杆，继续拆。
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    //加速
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int a,b,c,d;
        cin>>a>>b>>c>>d;
        add(a,b,c,d);
        add(b,a,c,d);
    }

    memset(dis,0x3f,sizeof(dis));
    //初始化dis为无穷大
    dis[1]=0;
    q2.push(make_pair(dis[1],1));
    //往q_2中加入起点，
    //经过copy_queue()后就在 q 中了
    dij(0);//从不拆限高杆开始枚举

    cout<<maxn-minn;
    return 0;
}