萌新求问 dijkstra 哪里写挂了 | 只对了#5

链式前向星存图 + 手写堆

#include<bits/stdc++.h>
#define LL long long 
using namespace std;
const int ML=1e5+9;
LL n,m,s,dis[ML];
LL pq[ML],top,vis[ML];
LL to[ML*2],wei[ML*2],nxt[ML*2],head[ML];
void add_edge(int x,int y,int z,int id);
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,0x3f,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]=s;
    dis[s]=0;
    while(top>0){
        int u=heap_get(1);
        vis[u]=true;
        for(int i=head[u];i;i=nxt[i])
            if(dis[u]+wei[i]<dis[to[i]]){
                dis[to[i]]=dis[u]+wei[i];
                if(!vis[to[i]]){
                    pq[++top]=to[i];
                    vis[to[i]]=true;
                    heap_up(top);
                }
            }
        heap_down(1);
    }
    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/2;
    while(ht>0){
        if(wei[pq[id]]<wei[pq[ht]]){
            swap(pq[id],pq[ht]);
            id=ht; ht=id/2;
        }
        else break;
    }
}
void heap_down(int id){
    int ht=id*2;
    while(ht<=top){
        if(ht+1<=top&&wei[pq[ht]]>wei[pq[ht+1]]) ht++;
        if(wei[pq[id]]>wei[pq[ht]]){
            swap(pq[id],pq[ht]);
            id=ht; ht=id*2;
        }
        else break;
    }
}
int heap_get(int id){
    int hg=pq[id];
    pq[id]=pq[top],top--;
    heap_down(id);
    return hg;
}