Dijkstra堆优化学习

最短路径例题

今天特地学习了Dijkstra的堆优化(主要是慕名已久)。

我们需要一个堆来记录[编号，到编号这个点的最短路径值(当然只是当前的)]

与原来的Dijkstra操作基本一致，主要有以下几点：

1.将起点放入堆中

2.开始while循环

3.取出堆顶

4.如果已经拓展过就continue

5.松弛操作同时满足条件放入堆

6.repeat step3

code：

#include <cstdio>

#include <queue>

#include <vector>

using namespace std;

struct node{

    int val,num;

    bool operator <(const node &x) const {

        return val>x.val;

    }

};

priority_queue< node > dij;

vector <pair<int,int> >a[];

int n,m,s,dist[],done[];

int main(){

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

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

            int x,y,c;

            scanf("%d%d%d",&x,&y,&c);

            a[x].push_back(make_pair(y,c));

        }

        for(int i=;i<=n;i++)dist[i]=;

    dist[s]=;

    dij.push((node){,s});

        while(!dij.empty()){

            int front=dij.top().num;

            dij.pop();

            if(done[front])continue;

            done[front]=true;

                for(int i=;i<a[front].size();i++){

                    int to=a[front][i].first,vl=a[front][i].second;

                    if(!done[to]&&dist[front]+vl<dist[to]){

                        dist[to]=dist[front]+vl;

                        dij.push((node){dist[to],to});

                    }

                }

        }

        for(int i=;i<=n;i++)printf("%d ",dist[i]);

    return ;

}