Dijkstra优化

#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;
}