配对堆优化Dijkstra算法小记

关于配对堆的一些小姿势：

1、配对堆是一颗多叉树。

2、包含优先队列的所有功能，可用于优化Dijkstra算法。

3、属于可并堆，因此对于集合合并维护最值的问题很实用。

4、速度快于一般的堆结构（左偏树,斜堆,随机堆……），具体时间复杂度：

合并（Merge）：$O(1)$；
插入（Insert/Push）：$O(1)$；
修改值（Change）：$O(1) \sim O(\log n)$；
取出维护的最值（Top）：$O(1)$；
弹出堆顶元素（Pop）：$O(\log n)$；

以下是配对堆优化Dijkstra算法的AC代码：

#include<bits/stdc++.h>

#include<ext/pb_ds/priority_queue.hpp>

using namespace std;

using namespace __gnu_pbds;

typedef pair<int,int> pii;

typedef __gnu_pbds::priority_queue<pii,greater<pii>,pairing_heap_tag> Heap;

const int maxn=1e5+;

const int INF=0x3f3f3f3f;

int n,m,s;

struct Edge{

    int u,v,w;

    Edge(int _u=,int _v=,int _w=){u=_u,v=_v,w=_w;}

};

vector<Edge> E;

vector<int> G[maxn];

void addedge(int u,int v,int w)

{

    E.push_back(Edge(u,v,w));

    G[u].push_back(E.size()-);

}

int d[maxn];

void dijkstra()

{

    memset(d,0x3f,sizeof(d));

    Heap Q;

    Heap::point_iterator id[maxn];

    d[s]=;

    id[s]=Q.push(make_pair(d[s],s));

    while(!Q.empty())

    {

        int u=Q.top().second; Q.pop();

        for(int i=;i<G[u].size();i++)

        {

            Edge &e=E[G[u][i]]; int v=e.v;

            if(d[v]>d[u]+e.w)

            {

                d[v]=d[u]+e.w;

                if(id[v]!=) Q.modify(id[v],make_pair(d[v],v));

                else id[v]=Q.push(make_pair(d[v],v));

            }

        }

    }

}

int main()

{

    scanf("%d%d%d",&n,&m,&s);

    for(int i=;i<=m;i++)

    {

        int u,v,w;

        scanf("%d%d%d",&u,&v,&w);

        addedge(u,v,w);

    }

    dijkstra();

    for(int i=;i<=n;i++) printf("%d%s",d[i],((i==n)?"\n":" "));

}

巴特西

配对堆优化Dijkstra算法小记

最新文章

热门文章