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

· · 题解

题目传送门

题目大意：

给定一个 n ， m ，表示路口数量和道路的段数。接下来 m 行，每行四个整数 a ， b ， c ， d ，表示路口 a 和路口 b 之间有一段长度为 c 的道路。如果 d 为 0 ，表示这段道路上没有限高杆, 如果 d 为 1 ，表示这段道路上有限高杆(不能走)。求出拆除两个或一个限高杆后，从 1 到 n 最多可以减少多少距离。

大致思路：

和先前的最短路一样建边，再存一下有没有限高杆，图就建好了。注意要建双向边，接下来就是遍历图，求出拆除一个或两个限高杆的最短距离，用没有拆除限高杆的最短距离减去即可。

本题核心：

如何求拆除一个或两个限高杆的最短距离。
我们可以用一个计数器，记录当前拆了多少个限高杆，再判断一下当前是否可以拆杆，加上最短路的判断。用封装结构体存下来，按走的道路的长度排下序，跑一遍 dij 即可。一些小细节看代码注释。

核心代码:

void dij()
{
    memset(dis , 0x3f , sizeof(dis)); //初始化 
    dis[1][0] = 0; //设一维为x，二维为y，指的是拆了y个杆后到x的最短距离 
    q.push(Node(1 , 0 , 0)); //封装结构体小根堆 
    while(!q.empty())
    {
        int x = q.top().x; //x是当前节点 
        int k = q.top().k; //k是当前拆了多少个杆 
        q.pop();
        if(vis[x][k]) continue; // vis数组含义和dis数组一样，存的是是否访问过 
        vis[x][k] = 1;
        for(register int i = head[x] ; i ; i = e[i].net) // 链式前向星遍历 
        {
            int to = e[i].to , w = e[i].w , f = e[i].xz; // f是是否有杆，有则k加1 
            if(k + f <= 2 && dis[x][k] + w < dis[to][k + f]) //当前拆的杆不能超过限制 
            {
                dis[to][k + f] = dis[x][k] + w;
                q.push(Node(to , k + f , dis[to][k + f]));
            }
        }
    }
}

代码如下：

#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>

using namespace std;
inline int read()
{
    int s = 0 , w = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9'){if(ch == '-') w = -1; ch = getchar();};
    while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0'; ch = getchar();};
    return s * w;
}
int n , m , cnt , sum1 , sum2;
struct node
{
    int to , net , w , xz;
    node(){xz = 0;} //初始化标记数组 
}e[(int)2e5 + 10];
int head[(int)1e4 + 10] ,  dis[(int)1e4 + 10][5] , vis[(int)1e4 + 10][5];
struct Node // 封装结构体小根堆 
{
    int x , k , v;
    Node(int X , int K , int V)
    {x = X , k = K , v = V;}
};
bool operator<(const Node &ix , const Node &iy)
{
    return ix.v > iy.v;
}
priority_queue <Node> q;
inline void add(int x , int y , int z , int f) //链式前向星存图，也可以用vector存 
{
    e[++cnt].w = z;
    e[cnt].to = y;
    e[cnt].xz = f;
    e[cnt].net = head[x];
    head[x] = cnt;
}
void dij()
{
    memset(dis , 0x3f , sizeof(dis)); //初始化 
    dis[1][0] = 0; //设一维为x，二维为y，指的是拆了y个杆后到x的最短距离 
    q.push(Node(1 , 0 , 0)); //封装结构体小根堆 
    while(!q.empty())
    {
        int x = q.top().x; //x是当前节点 
        int k = q.top().k; //k是当前拆了多少个杆 
        q.pop();
        if(vis[x][k]) continue; //vis数组含义和dis数组一样，存的是是否访问过 
        vis[x][k] = 1;
        for(register int i = head[x] ; i ; i = e[i].net) //链式前向星遍历 
        {
            int to = e[i].to , w = e[i].w , f = e[i].xz; // f是是否有杆，有则k加1 
            if(k + f <= 2 && dis[x][k] + w < dis[to][k + f]) //当前拆的杆不能超过限制 
            {
                dis[to][k + f] = dis[x][k] + w;
                q.push(Node(to , k + f , dis[to][k + f]));
            }
        }
    }
}
int main()
{
    n = read() , m = read();
    for(register int i = 1 ; i <= m ; i++)
    {
        int u = read() , v = read() , z = read() , f = read();
        add(u , v , z , f); //建双向边 
        add(v , u , z , f);
    }
    dij();
    cout << dis[n][0] - min(dis[n][1] , dis[n][2]); //有可能有只有一个杆的情况，取最小值 
    return 0;
}