堆优化dijkstra

单源最短路径

题目链接：https://www.luogu.org/problemnew/show/P4779

直到做了这个题才发现我之前写的堆优化dijkstra一直是错的。。

这个堆优化其实很容易理解，将枚举最小值改为从堆中取出最小值，改变dis时入堆即可

用单调队列维护时必须有两个值：点的编号和当前的距离

以距离为标准从小到大排序，每次去除最小的

以前错的原因：

堆中只维护了点的编号，以dis[x]排序

这样做在取出一个元素操作后，会更新它周围一圈元素的dis值，

若它周围一圈元素中有的在堆中，dis值被改变后，堆的性质会遭到破坏

然而由于这道题太水了，我一直认为这是对的

#include<iostream>

#include<cstring>

#include<cstdio>

#include<queue>

using namespace std;

#define il inline

#define re register

#define N 100010

#define M 200010

int n,m,s,dis[N];

struct FUCK{

    int p;

    int cost;

};

struct cmp{

    il bool operator()(FUCK ZYX,FUCK YSH){

        return ZYX.cost>YSH.cost;

    }

};

priority_queue<FUCK,vector<FUCK>,cmp> q;

il int read(){

    int x=; char c=getchar();

    while(c<''||c>'') c=getchar();

    while(''<=c&&c<='') { x=(x<<)+(x<<)+c-''; c=getchar(); }

    return x;

}

void write(int x){

    if(x>) write(x/);

    putchar(x%+'');

}

struct NODE{

    int to,w,next;

} e[M];

int Head[N],num;

il void add(int x,int y,int w){

    e[++num].to=y;

    e[num].w=w;

    e[num].next=Head[x];

    Head[x]=num;

}

bool used[N];

int main()

{

    n=read(); m=read(); s=read();

    int x,y,w;

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

        x=read(); y=read(); w=read();

        add(x,y,w);

    }

    memset(dis,,sizeof(dis));

    dis[s]=;

    q.push((FUCK){s,});

    while(!q.empty()){

        FUCK k=q.top();

        q.pop();

        int u=k.p;

        if(used[u]) continue;

        used[u]=;

        for(re int i=Head[u];i;i=e[i].next){

            int v=e[i].to;

            if(dis[v]>dis[u]+e[i].w){

                dis[v]=dis[u]+e[i].w;

                q.push(FUCK{v,dis[v]});

            }

        }

    }

    for(re int i=;i<=n;i++)

     write(dis[i]),putchar(' ');

    return ;

}

巴特西

堆优化dijkstra

最新文章

热门文章