[蓝桥杯 2020 省 AB3] 限高杆

· · 题解

大意

货车要从 1 号点开到 n 号点，有限高杆的路走不了，能拆掉两个限高杆，问拆除前后的路程之差最大为多少。

分析

很明显这是一道最短路的题（如果最短路不知道的看这个，最短路，大佬写的特别好 orz），问题就在于拆杆，这里有一点 dp 的思想，我们把不拆杆，拆一个杆，和拆两个杆分为三个不同的状态，在 dist 数组里面分别存储，最短路时从 1 号点开始扫，如果当前的路有一个限高杆，那么把结果存在拆一个杆的状态里，如果有两个限高杆，那么把结果存在拆两个杆的状态里，没有就存在没拆的状态里，如果超过两个就直接跳过，其余的求最短路的过程和模板一样，这样最短路时的参数会比较多，不过更清晰，这里我使用了 dijkstra 加堆优化来求最短路。

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int n,m,x,y,z,d[11111][3],w,w1;//后面一维表示拆掉几个杆
bool vis[111111][3],b;
struct f{
    int i,s;
    bool b;//i 是编号，s 是边权，b 是这条路上有没有杆子
};
vector<f> a[111111];
void dji()
{
    memset(d,127,sizeof(d));
    priority_queue<pair<int,pair<int,int> >,vector<pair<int,pair<int,int> > >,greater<pair<int,pair<int,int> > > > q;//三个参数分别是，最短路长度，目前拆了几个杆，当前节点的编号
    d[1][0]=0;
    q.push({0,{0,1}});
    while(q.size())//模板，只差了一维
    {
        w=q.top().second.second;
        w1=q.top().second.first;
        q.pop();
        if(vis[w][w1]) continue;
        vis[w][w1]=1;
        for(int i=0;i<a[w].size();i++)
        {
            if(a[w][i].b+w1>2) continue;//如果拆了超过两根杆就直接跳过
            if(d[a[w][i].i][a[w][i].b+w1]>d[w][w1]+a[w][i].s)
            {
                d[a[w][i].i][a[w][i].b+w1]=d[w][w1]+a[w][i].s;
                q.push({ d[a[w][i].i][a[w][i].b+w1] , {a[w][i].b+w1 , a[w][i].i } });
            }
        }
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        cin>>x>>y>>z>>b;
        a[x].push_back((f){y,z,b});
        a[y].push_back((f){x,z,b});//别忘了建双向图
    }
    dji();
    cout<<d[n][0]-min(d[n][1],min(d[n][2],d[n][0]));//求不拆杆和拆杆时路程的最大差值
    return 0;
}