Dijkstra优化

pengyulun · 2025-08-15 14:30:46 · 算法·理论

时间复杂度：o(n·logm) \to o(n·logn+m)

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int MAXN=1<<18,N=1e6+8,M=3e6+8;
char *p1,*p2,buf[MAXN],buffer[MAXN];
int q1=-1,q2=MAXN-1,j=0;
ll ans[N],C=0x3f3f3f3f3f3f3f3f;
int n,m,h[N],cnt=0,w[N];
struct G{int x,t;ll u;} a[M<<1];
#define getchar_fread() (p1==p2&&(p2=(p1=buf)+fread(buf,1,MAXN,stdin),p1==p2)?EOF:*p1++)
#define flush() (fwrite(buffer,1,q1+1,stdout),q1=-1)
template<typename T>
inline void read(T &x){
    x=0;
    T c=getchar_fread();
    while(!isdigit(c)) c=(T)getchar_fread();
    while(isdigit(c)) x=(x<<3)+(x<<1)+c-48,c=(T)getchar_fread();
}
inline void putchar_fwrite(char x){if (q1==q2) flush();buffer[++q1]=x;}
template<typename T>
inline void write(T x){
    T print[65];
    while (x) print[++j]=x%10,x/=10;
    if (j==0) print[++j]=0;
    while (j) putchar_fwrite(print[j--]+48);
}
struct priority_queue{
    int _q[N],_p[N],sz=0;
    ll sta[N];
    inline void pop(){
        int t=1;
        swap(sta[1],sta[sz]);
        swap(_q[1],_q[sz]);
        _q[sz]=sta[sz]=0;--sz;
        while ((t<<1)<=sz){
            int p=(t<<1)+((t<<1|1)>sz||sta[t<<1]<sta[t<<1|1]?0:1);
            if (sta[t]<sta[p]) break;
            _p[_q[p]]=t;
            swap(sta[t],sta[p]);swap(_q[t],_q[p]);t=p;
        }
        _p[_q[t]]=t;
    }
    inline void push(int k){
        sta[++sz]=ans[k];int t=sz;_q[sz]=k;
        while (t>1&&sta[t]<sta[t>>1]) 
            swap(sta[t],sta[t>>1]),swap(_q[t],_q[t>>1]),_p[_q[t]]=t,t>>=1;
        _p[k]=t;
    }
    inline void add(int k){
        int t=_p[k];
        sta[t]=ans[k];
        while (t>1&&sta[t]<sta[t>>1]) 
            swap(sta[t],sta[t>>1]),swap(_q[t],_q[t>>1]),_p[_q[t]]=t,t>>=1;
        _p[k]=t;
    }
    inline int top(){return _q[1];}
    inline bool empty(){return sz;}
} sta;
inline void Dijkstra(int s){
    memset(ans,C,sizeof(ans));
    memset(w,0,sizeof(w));
    ans[s]=0,sta.push(s);
    while (sta.empty()){
        int u=sta.top();sta.pop();
        for (int i=h[u];i;i=a[i].t)
            if (ans[a[i].x]>ans[u]+a[i].u){
                ans[a[i].x]=ans[u]+a[i].u;
                if (w[a[i].x]) sta.add(a[i].x);else w[a[i].x]=1,sta.push(a[i].x);}
    }
}
signed main(){
    int s;ll z;
    read(n),read(m),read(s);
    for (int i=1,x,y;i<=m;++i){
        read(x),read(y),read(z);
        a[++cnt]={y,h[x],z};h[x]=cnt;
    }
    Dijkstra(s);
    for (int i=1;i<=n;++i) write(ans[i]),putchar_fwrite(' ');
    flush();
    return 0;
}