Dijkstra优先队列优化

模板题：

SDU-ACM 2021 模板整理 1 - Virtual Judge (vjudge.net)

kuangbin板子代码

#include<bits/stdc++.h>
using namespace std;

const int MAXN=1e5+7,MAXM=5e5+7,INF=0x3f3f3f3f;
struct qnode{
    int v,c;
    qnode(int _v=0,int _c=0){
        v=_v;c=_c;
    }
    bool operator <(const qnode &r ) const {
        return c<r.c;
    }
};
struct Edge{
    int v,cost;
    Edge(int _v=0,int _cost=0){
        v=_v;cost=_cost;
    }
};
struct cmp {
    bool operator ()(qnode x,qnode y){
        return !(x<y);
    }
};
vector<Edge>E[MAXM];
bool vis[MAXN];
int dist[MAXN];
void Dijkstra(int n,int start){
    memset(vis,false,sizeof(vis));
    for(int i=0;i<=n;++i)   dist[i]=INF;
    priority_queue<qnode,vector<qnode>,cmp>   que;
    while(!que.empty()) que.pop();
    dist[start]=0;
    que.push(qnode(start,0));
    qnode temp;
    while(!que.empty()){
        temp=que.top();
        que.pop();
        int u=temp.v;
        if(vis[u])  continue;
        vis[u]=true;
        for(int i=0;i<E[u].size();++i){
            int v=E[u][i].v;
            int cost=E[u][i].cost;
            if(!vis[v]&&dist[v]>dist[u]+cost){
                dist[v]=dist[u]+cost;
                que.push(qnode(v,dist[v]));
            }
        }
    }
}
void addedge(int u,int v,int w){
    E[u].push_back(Edge(v,w));
}
//void init(){
//    for(int )
//}
int m,n,r;
int main(){
    cin>>n>>m>>r;
    for(int i=1;i<=m;++i){
        int x,y,z;
        cin>>x>>y>>z;
        addedge(x,y,z);
    }
    Dijkstra(n,r);
    for(int i=0;i<n;++i){
        if(dist[i]!=INF)
            cout<<dist[i]<<endl;
        else
            cout<<"INF"<<endl;
    }
}

坑

1.优先队列默认是大根堆，也就是说默认是从大到小排序的

2.优先队列使用方法

struct cmp {
    bool operator ()(qnode x,qnode y){
        return !(x<y);
    }
};

priority_queue<qnode,vector<qnode>,cmp>   que;

Dijkstra堆优化kuangbin模板

原文：https://www.cnblogs.com/sora-13/p/14715128.html