优化版dijkstar

LH0310 · 2019-07-07 16:44:30 · 个人记录

优化版dijkstar

P4779 【模板】单源最短路径（标准版）

#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
const int maxn=100010,maxm=200010;
struct edge{
    int dot,w;
}E[maxm];
int head[maxn],next[maxm],d[maxn];
bool v[maxn];
bool operator <(const edge &P,const edge &Q){
    return P.w>Q.w;
}
int n,m,s,id=0;
edge a,b;
void add(int s,int e,int w){
    E[++id].dot=e;
    E[id].w=w;
    next[id]=head[s];
    head[s]=id;
}
void dijkstra(int s){
    priority_queue <edge> Q;
    memset(d,0x3f,sizeof(d));
    memset(v,true,sizeof(v));
    d[s]=0;
    a.dot=s,a.w=0;
    Q.push(a);
    while(!Q.empty()){
        if(!v[Q.top().dot]){
            Q.pop();
            continue;
        }

        b=Q.top();
        Q.pop();
        int x=b.dot;
        v[x]=false;
        d[x]=b.w;
        for(int i=head[x];i;i=next[i]){
            int y=E[i].dot;
            if(d[y]>d[x]+E[i].w && v[y]){

                d[y]=d[x]+E[i].w;
                b.dot=y,b.w=d[y];
                Q.push(b);
            }
        }
    }
}
int main(){
    cin>>n>>m>>s;
    for(int i=1;i<=m;i++){
        int s,e,w;
        cin>>s>>e>>w;
        add(s,e,w);
    }
    dijkstra(s);
    for(int i=1;i<=n;i++)
        cout<<d[i]<<' ';
    return 0;
}

简单说，就是利用优先队列和链式前向星提高效率