限高杆——dijkstra二维扩展大法

思路

dijkstra求最短路，如果没有杆子的限制，这题我们肯定是能直接用dijkstra,spfa等方法直接做的。坏就坏在这题有一些边是不能通过的，但是我们有两次强行通过的机会，于是我们得在合适的位置使用这两次机会。然而，通过思考我们可以发现，我们是无法找出具体在哪两个位置使用的这两次机会的。所以，我们只能把所有的情况都扩展出来，然后找到路径最小的那一条。

如何实现

实现的方法很简单，对于朴素的dijkstra算法，我们是使用了一个dist[N]数组来存储每一个点到原点的距离。现在，我们有两次强行通过的机会。也就是说，我们每到一个点，也许会存在3种情况，到N这个点时，剩余0，1，2次强行通过机会。所以，我们把dist[N]数组扩展成二维的dist[N][3]就能够完美的表示所有的情况。于是，我们在dijkstra扩展边时就分两种情况扩展：一种是没有杆子，另外一种是有杆子，代码如下

        for(int i=h[ver];i!=-1;i=ne[i])//遍历邻边
        {
            int j=e[i];
            if(gan[i]&&times==0) continue;
            if(gan[i]&&times>=1)//当有杆子挡住时，看有没有拆除次数
            {
                if(dist[j][times-1]>dist[ver][times]+w[i])
                {
                    dist[j][times-1]=dist[ver][times]+w[i];
                    heap.push({dist[j][times-1],j,times-1});
                }
            }//没有杆子挡住时，就是按正常的dijkstra方法扩展边
            else if(gan[i]==0&&dist[j][times]>dist[ver][times]+w[i])
            {
                dist[j][times]=dist[ver][times]+w[i];
                heap.push({dist[j][times],j,times});
            }
        }

C++ 代码

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
const int N=10010,M=200010,INF=0x3f3f3f3f;
int h[N],e[M],ne[M],w[M],gan[M],idx;
int dist[N][3];//扩展成二维层面，走到这个点时，拥有不同的通过次数，属于不同的情况
bool st[N][3];//dist[x][y]表示到x这个点时，还有y次通过次数（拆除桥的次数）
int n,m;
void add(int a,int b,int c,int d)
{
    e[idx]=b,w[idx]=c,gan[idx]=d,ne[idx]=h[a],h[a]=idx++;
}
struct Node
{
    int d,ver,times;//距离起始点的距离，节点编号，剩余通过次数
    bool operator <(const Node&N) const
    {
        return d>N.d;//从小到大排序，优先队列与sort相反
    }
};
int dijkstr()
{
    memset(dist,0x3f,sizeof dist);
    priority_queue <Node> heap;//优先队列，按到原点距离从小到大排序
    heap.push({0,1,2});
    dist[1][2]=0;//出发点距离为0

    while(heap.size())
    {
        auto t=heap.top();
        heap.pop();
        int d=t.d,ver=t.ver,times=t.times;
        if(st[ver][times]) continue;
        st[ver][times]=true;

        for(int i=h[ver];i!=-1;i=ne[i])//遍历邻边
        {
            int j=e[i];
            if(gan[i]&&times==0) continue;
            if(gan[i]&&times>=1)//当有杆子挡住时，看有没有拆除次数
            {
                if(dist[j][times-1]>dist[ver][times]+w[i])
                {
                    dist[j][times-1]=dist[ver][times]+w[i];
                    heap.push({dist[j][times-1],j,times-1});
                }
            }//没有杆子挡住时，就是按正常的dijkstra方法扩展边
            else if(gan[i]==0&&dist[j][times]>dist[ver][times]+w[i])
            {
                dist[j][times]=dist[ver][times]+w[i];
                heap.push({dist[j][times],j,times});
            }
        }
    }
    //最大值一定是dist[n][2]，且dist[n][2]一定存在;最小值不一定是dist[n][0]因为dist[n][0]不一定存在
    int res=min(dist[n][0],min(dist[n][1],dist[n][2]));
    return dist[n][2]-res;
}
int main()
{
    cin>>n>>m;
    memset(h,-1,sizeof h);
    while(m--)//存双向边，既要存储边的长度，还要记录是否的杆子挡住
    {
        int a,b,c,d;
        cin>>a>>b>>c>>d;
        add(a,b,c,d),add(b,a,c,d);
    }
    cout<<dijkstr()<<endl;
    return 0;
}