WA求助（心血来潮手打了堆，结果除了样例全WA了）

咸咸咸鱼 @ 2023-07-12 16:43:57

#include <cstdio>
using namespace std;
const int maxn=2e5+10;
struct edge{
    int u,v,w;
}e[maxn<<2];
int tail[maxn],cnt;
void add(int u,int v,int w){
    e[++cnt].v=v;
    e[cnt].w=w;
    e[cnt].u=tail[u];
    tail[u]=cnt;
}
struct Heap{
    int siz;
    struct node{
        int id,w;
    }h[maxn<<1];
    void swap(node a,node b){
        node c=a;
        a=b,b=c;
    }
    void push(int id,int w){
        siz++;
        h[siz].id=id,h[siz].w=w;
        int u=siz;
        while(u){
            int v=u>>1;
            if(h[u].w<h[v].w) swap(h[u],h[v]);
            else break;
            u=v;
        } 
    }
    void pop(){
        swap(h[1],h[siz]);
        siz--;
        int u=1;
        while((u<<1)<=siz){
            int v=u<<1;
            if(v+1<=siz && h[v].w>=h[v+1].w) v++;
            if(h[u].w>h[v].w) swap(h[u],h[v]);
            else break;
            u=v;
        }
    }
    bool empty(){
        if(siz<=0) return 1;
        else return 0;
    }
    int top(){
        return h[1].id;
    }
}q;
int n,m,s;
int dis[maxn],vis[maxn];
void Dij(int s){
    q.push(s,0);
    dis[s]=0;
    vis[s]=1;
    while(!q.empty()){
        int u=q.top();
        q.pop();
        vis[u]=1;
        for(int i=tail[u];i;i=e[i].u){
            int v=e[i].v;
            if(dis[v]>dis[u]+e[i].w){
                dis[v]=dis[u]+e[i].w;
                if(!vis[v]){
                    q.push(v,dis[v]);
                    vis[v]=1;
                }
            }
        }
        vis[u]=0;
    }
}
int main(){
    scanf("%d%d%d",&n,&m,&s);
    for(int i=1;i<=n;i++){
        dis[i]=1e9+114;
    }
    for(int i=1;i<=m;i++){
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        add(u,v,w);
    }
    Dij(s);
    for(int i=1;i<=n;i++){
        printf("%d ",dis[i]);
    }
    return 0;
}

by EcHO_714 @ 2023-07-19 20:56:42

@咸咸咸鱼 你的 swap 函数在运行时会出错，建议每次交换都手动写一遍，尽量不要用swap，有坑

by EcHO_714 @ 2023-07-19 21:00:36

@咸咸咸鱼

#include <cstdio>
using namespace std;
const int maxn=2e5+10;
struct edge{
    int u,v,w;
}e[maxn<<2];
int tail[maxn],cnt;
void add(int u,int v,int w){
    e[++cnt].v=v;
    e[cnt].w=w;
    e[cnt].u=tail[u];
    tail[u]=cnt;
}
struct Heap{
    int siz;
    struct node{
        int id,w;
    }h[maxn<<1];
    void push(int id,int w){
        siz++;
        h[siz].id=id,h[siz].w=w;
        int u=siz;
        while(u){
            int v=u>>1;
            if(h[u].w<h[v].w){
                node c=h[u];
                h[u]=h[v],h[v]=c;
            }
            else break;
            u=v;
        } 
    }
    void pop(){
        node c=h[1];
        h[1]=h[siz],h[siz]=c;
        siz--;
        int u=1;
        while((u<<1)<=siz){
            int v=u<<1;
            if(v+1<=siz && h[v].w>=h[v+1].w) v++;
            if(h[u].w>h[v].w){
                node c=h[u];
                h[u]=h[v],h[v]=c;
            }
            else break;
            u=v;
        }
    }
    bool empty(){
        if(siz<=0) return 1;
        else return 0;
    }
    int top(){
        return h[1].id;
    }
}q;
int n,m,s;
int dis[maxn],vis[maxn];
void Dij(int s){
    q.push(s,0);
    dis[s]=0;
    vis[s]=1;
    while(!q.empty()){
        int u=q.top();
        q.pop();
        vis[u]=1;
        for(int i=tail[u];i;i=e[i].u){
            int v=e[i].v;
            if(dis[v]>dis[u]+e[i].w){
                dis[v]=dis[u]+e[i].w;
                if(!vis[v]){
                    q.push(v,dis[v]);
                    vis[v]=1;
                }
            }
        }
        vis[u]=0;
    }
}
int main(){
    scanf("%d%d%d",&n,&m,&s);
    for(int i=1;i<=n;i++){
        dis[i]=1e9+114;
    }
    for(int i=1;i<=m;i++){
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        add(u,v,w);
    }
    Dij(s);
    for(int i=1;i<=n;i++){
        printf("%d ",dis[i]);
    }
    return 0;
}

这是修改后的代码（已AC）

by EcHO_714 @ 2023-07-19 21:06:25

@咸咸咸鱼 能不能帮忙看看我的 手写堆 为什么是 32pts ，去年调到现在了qwq

by EcHO_714 @ 2023-07-19 21:07:24

提交记录里搜 528764 就好了qwq

by 咸咸咸鱼 @ 2023-08-01 08:29:51

@EcHO_714 好像Dijkstra有点问题？我改了一下过了84pt，但是第一个点TLE了，这个属于是真的搞不懂了QAQ

by 咸咸咸鱼 @ 2023-08-01 08:31:25

@EcHO_714

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int ML=1e6+9;
struct Het{
    int val,key;
}pq[ML<<2];
int n,m,s,dis[ML],vis[ML],top;
int to[ML],wei[ML],nxt[ML],head[ML];
void add_edge(int x,int y,int z,int id);
void sp(Het &x,Het &y);
void heap_up(int id);
void heap_down(int id);
int heap_get(int id);
int main(){
    // freopen("usd.in","r",stdin);
    // freopen("usd.out","w",stdout);
    cin>>n>>m>>s;
    memset(dis,0x7f,sizeof(dis));
    for(int i=1;i<=m;i++){
        int u,v,w;
        cin>>u>>v>>w;
        add_edge(u,v,w,i);
    }
/*->*/pq[++top].key=s;
    pq[top].val=0;
    dis[s]=0;
    vis[s]=1;
    while(top){
        int u=heap_get(1);
        vis[u]=true;
        for(int i=head[u];i;i=nxt[i]){
            int v=to[i],w=wei[i];
            if(dis[v]>dis[u]+w){
                dis[v]=dis[u]+w;
                if(!vis[v]){
                    pq[++top]=(Het){dis[v],v};
                    heap_up(top);
                    vis[v]=1;
                }
            }
        }
        vis[u]=false;  
/*->*/}
    for(int i=1;i<=n;i++) cout<<dis[i]<<" ";
    return 0;
}
void add_edge(int x,int y,int z,int id){
    nxt[id]=head[x];
    to[id]=y; wei[id]=z;
    head[x]=id;
}
void heap_up(int id){
    int ht=id>>1;
    while(ht){
        if(pq[id].val<pq[ht].val){
            sp(pq[id],pq[ht]);
            id=ht; ht=id>>1;
        }
        else break;
    }
}
void heap_down(int id){
    int ht=id<<1;
    while(ht<=top){
        if(ht+1<=top&&pq[ht].val>pq[ht+1].key) ht++;
        if(pq[id].val>pq[ht].val){
            sp(pq[id],pq[ht]);
            id=ht; ht=id<<1;
        }
        else break;
    }
}
int heap_get(int id){
    int hg=pq[id].key;
    pq[id]=pq[top],top--;
    heap_down(id);
    return hg;
}
void sp(Het &x,Het &y){
    Het  z=x;
    x=y; y=z;
}