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

Lamb_Carp · 2023-09-11 23:51:43 · 题解

题意分析

在这个题中我们可以知道，如果这条路有限高杆的话，那么就不允许同行，但是如果没有则可以通行。

限高杆最多只可以拆两个。

有了这两个条件我们就可以从集合的角度进行分析（这样子可以保证不重不漏）：

• 首先，我们在面对一个杆的时候我们会有两种决策：

  1. 我当前拆卸的杆数还没有到达 2，那么我可以拆掉这个杆子并通行。

  2. 我不愿意拆这个杆子（不论我拆的数量是否到达 2），那么我就直接跳过，然后绕路走。

• 之后，如果我们面对的是一个没有杆子的道路：

  3. 我直接对这个最短路进行常规操作，正常更新。

分析到这里，大家大概也就明白，这是一个分层图的题，或者可以是一个动态规划 + 最短路的题目，具体做法看个人癖好。（我个人喜欢对分层图的题全部当成动态规划 + 最短路）。

最后需要留个心眼，比如说它拆了这条路的限高杆，但是这条路比其他路加起来还要长，这样子拆了还不如不拆，所以说，最后答案我们需要在这个拆一个和拆两个里面取最小值，然后我们再用一次也不拆的最小值减去这个最小值，就得到我们的正确答案了。

下面则是给那些自己敲了一遍，不断检查代码但是还是感觉是题目的问题（“多对的代码啊~可它就是不对~”） 的同学们的一些小帮助。

CODE TIME

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define rl register ll

const ll N = 1e4 + 10, M = 2e5 + 10;

ll n, m;

ll tot, ne[M], e[M], h[N], w[M], dis[N][3], sta[M];

bool st[N][3];

struct node
{
    ll id, dis, type;
    bool operator <(const node &x) const
    {
        return dis > x.dis;
    }
};

priority_queue<node> q;

inline void add(ll a, ll b, ll c, ll d)
{
    ne[++tot] = h[a], h[a] = tot, e[tot] = b, w[tot] = c, sta[tot] = d;
}

inline void dij(ll s)
{
    memset(dis, 0x3f, sizeof dis);
    memset(st, 0, sizeof st);

    dis[s][0] = dis[s][1] = dis[s][2] = 0;

    q.push({s, 0, 0});

    while(q.size())
    {
        node asd = q.top();
        q.pop();
        ll u = asd.id, t = asd.type, dist = asd.dis;
        if(st[u][t]) continue;
        st[u][t] = 1;
        for(rl i=h[u]; ~i; i = ne[i])
        {
            ll v = e[i];
            if(sta[i] && t <= 1)
            {
                if(dis[v][t + 1] > dis[u][t] + w[i])
                {
                    dis[v][t + 1] = dis[u][t] + w[i];
                    q.push({v, dis[v][t + 1], t + 1});
                }
                else continue;
            }else if(!sta[i]) 
            {
                if(dis[v][t] > dis[u][t] + w[i])
                {
                    dis[v][t] = dis[u][t] + w[i];
                    q.push({v, dis[v][t], t});
                }
            }
        }
    }
}

int main()
{
    memset(h, -1, sizeof h);

    cin >> n >> m;

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

    dij(1);

    cout << dis[n][0] - min(dis[n][1], dis[n][2]) << endl;
    return 0;
}

完结撒花~感谢支持我的题解（高情商的人应该都懂我的意思）