\(dijkstra\) 算法的堆优化，时间复杂度为\(O(n+m)\log n\)

添加数组\(id[]\)记录某节点在堆中的位置，可以避免重复入堆从而减小常数

而这一方法需要依托手写堆

#include"cstdio"#include"cstring"#include"iostream"#include"algorithm"#include"bitset"using namespace std;const int MAXN=1e5+5;const int INF=2e9;int n,m,s,np;int hp[MAXN],h[MAXN],ln[MAXN],id[MAXN];struct rpg{    int li,nx,ln;}a[MAXN<<1];inline int read(){    int x=0;char ch=getchar();    while(ch<'0'||'9'
    
     >1;j;i=j,j>>=1){        if(ln[hp[i]]
     
      ln[hp[j]]) swap(hp[i],hp[j]),swap(id[hp[i]],id[hp[j]]);        else break;    }return;}void dijkstra(){    for(int i=1;i<=n;++i) ln[i]=INF;    ln[s]=0;ins(s);    while(hp[0]){        int nw=hp[1];pop();        for(int i=h[nw];i;i=a[i].li){            if(ln[a[i].nx]>ln[nw]+a[i].ln){                ln[a[i].nx]=ln[nw]+a[i].ln;                if(!id[a[i].nx]) ins(a[i].nx);                else up(id[a[i].nx]);            }        }    }return;}int main(){    n=read(),m=read(),s=read();    for(int i=1;i<=m;++i){        int x=read(),y=read(),z=read();        add(x,y,z);    }dijkstra();    for(int i=1;i<=n;++i) printf("%d ",ln[i]);    return 0;}