Dijistra求助,WA一个点。可能是自己编的堆出了问题

P4779 【模板】单源最短路径(标准版)

国国の国王 @ 2022-11-15 18:04:42

#include<bits/stdc++.h>
using namespace std;
const int Maxm=2e5+5,Maxn=1e5+5;
struct Edge{
    int u,v,w;
    int next;
}e[Maxm];
int top;
struct Dist{
    int v,w;//到V的距离是W 
}pile[Maxm+Maxn];
int pt;//ptop
int head[Maxn];
int dis[Maxn];
bool vis[Maxn];
int n,m;
void reset(){
    for(int i=1;i<=n;i++) dis[i]=2e9;
}
void Add(int u,int v,int w){
     top++;
     e[top].u=u;
     e[top].v=v;
     e[top].w=w;
     e[top].next=head[u];
     head[u]=top;
     return;
}
void Put(int v,int w){
    pile[++pt].v=v;
    pile[pt].w=w;
    int np=pt,fa=np/2;
    while(fa){
        if(pile[np].w>pile[fa].w) return;
        swap(pile[np],pile[fa]);
        np=fa;
        fa=np>>1;
    }
    return;
}
void Pop(){
    swap(pile[1],pile[pt]);
    pt--;
    int np=1,son=2;
    while(son<=pt){
        if(son<pt&&pile[son+1].w<pile[son].w) son++;
        if(pile[son].w<pile[np].w) return;
        swap(pile[np],pile[son]);
        np=son;
        son=np<<1;
    }
    return;
}
void Dijistra(int np){
    Put(np,0);
    while(pt){
        int v=pile[1].v,w=pile[1].w;
        Pop();
        if(vis[v]) continue;
        dis[v]=w;
        vis[v]=1;
        for(int i=head[v];i;i=e[i].next){
            if(vis[e[i].v]) continue;
            Put(e[i].v,w+e[i].w);
        }
    }
    return;
}
int main(){
    int u,v,w,s;
    scanf("%d%d%d",&n,&m,&s);
    reset();
    for(int i=1;i<=m;i++){
        scanf("%d%d%d",&u,&v,&w);
        Add(u,v,w);
    }
    Dijistra(s);
    for(int i=1;i<=n;i++) printf("%d ",dis[i]);
}

by yummy @ 2022-11-15 18:54:22

《Dijkstra 的 100 种拼法》


by 国国の国王 @ 2022-11-16 15:57:18

改正一下,题目是A一个点


by 国国の国王 @ 2022-11-16 16:15:32

@国国の国王

if(pile[son].w<pile[np].w) return;

已过,此贴终结


|