关于SPFA

/***************************************************
 以下代码包括了两种优秀的最短路算法——Dijkstra与SPFA
 它们在加上堆优化后都可以跑得飞快
 尽管它们相貌相似，但基于不同的原理 
 ***************************************************/
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#define PBCWZCC
using namespace std;
#define MAXN 100000
#define MAXM 400000
#define LL long long
#define DEBUG
#define MODIT
template<class T>inline void read(T&X)
{
    X=0;
    char symbol('\0'),ch(getchar());
    for(;ch<'0'||'9'<ch;(ch=='-')?(symbol='\1'):(1),ch=getchar());
    for(;'0'<=ch&&ch<='9';X=(X<<3)+(X<<1)+(ch^48),ch=getchar());
	(symbol)?(X=-X):(1);
}
template<class T>inline void swap_(T&A , T&B)
{
	T C(A);
	A = B;
	B = C;
}
int n,m;
LL dis[MAXN|3];
char vis[MAXN|3];
class node{
	public:
		int val;
		LL d;
		bool operator<(const node& b)const
		{
			return this->d < b.d;
		}
};
#ifndef opt_tree
#define opt_tree
#define fa(x) ((x)>>1)
#define lc(x) ((x)<<1)
#define rc(x) ((x)<<1|1)
#endif
class heap_{
	private:
		node val[MAXN|3];
		int tot;
	public:
		int size(void)
		{
			return tot;
		}
		void push(int x)
		{
			val[++tot].val = x;
			for(x=tot;1<x&&val[x]<val[fa(x)];swap_(val[x],val[fa(x)]),x=fa(x));
		}
		void push(int x,const LL dd)
		{
			val[++tot].val = x;
			val[tot].d = dd;
			for(x=tot;1<x&&val[x]<val[fa(x)];swap_(val[x],val[fa(x)]),x=fa(x));
		}
		int top(void)
		{
			return val[1].val;
		}
		LL topd(void)
		{
			return val[1].d;
		}
		void pop(void)
		{
			int x;
			val[1] = val[tot--];
			for(x=1;lc(x)<=tot&&val[lc(x)]<val[x];swap_(val[lc(x)],val[x]),x=lc(x));
			for(;rc(x)<=tot&&val[rc(x)]<val[x];swap_(val[rc(x)],val[x]),x=rc(x));
		}
};
heap_ Q;
class graph{
    public:
	    int heads[MAXN|1],cnt;
	    int next[MAXM|1],to[MAXM|1]; 
		LL W[MAXM|1];
	    graph(){cnt=0;}
		~graph(){}
	    void addE(int u,int v)
		{
			++cnt;
		    next[cnt] = heads[u];
		    to[cnt] = v;
		    heads[u] = cnt;
		}
		void addE(int u,int v,LL w)
		{
			++cnt;
		    next[cnt] = heads[u];
		    to[cnt] = v;
		    W[cnt] = w;
		    heads[u] = cnt;
		}
		void HPFA(int uu)
		{
			int vv;
			Q.push(uu,0);
			memset(dis,0x3f,sizeof dis);
			dis[uu] = 0;
			for(;Q.size();)
			{
				uu = Q.top();
				Q.pop();
				vis[uu] = '\0';
				for(int e(heads[uu]);e;e=next[e])
				{
					vv = to[e];
					if(dis[uu]+W[e]<dis[vv])
					{
						dis[vv] = dis[uu]+W[e];
						if(!vis[vv])
						{
							Q.push(vv,dis[vv]);
							vis[vv] = '\1';
						}
					}
				}
			}
		}
		void HPDJ(int uu)
		{
			int vv;
			LL dd;
			Q.push(uu,0);
			memset(dis,0x3f,sizeof dis);
			dis[uu] = 0;
			for(;Q.size();)
			{
				uu = Q.top();
				dd = Q.topd();
				Q.pop();
			DEBUG	fprintf(stderr,"(%d %lld)\n",uu,dd);
				if(dd!=dis[uu]) continue;
				vis[uu] = '\1';
				for(int e(heads[uu]);e;e=next[e])
				{
					vv = to[e];
					if(!vis[vv])
					{
						if(dis[vv]>dis[uu]+W[e])
						{
							dis[vv] = dis[uu]+W[e];
							Q.push(vv,dis[vv]);
						DEBUG	fprintf(stderr,"->  (%d %lld)\n",vv,dis[vv]);
						}
					}
				}
			}
		}
};
graph E;
int s;
int main()
{
	read(n);
	read(m);
	read(s);
	register int i(1);
	for(register int x,y,z;i<=m;++i)
	{
		read(x);
		read(y);
		read(z);
		E.addE(x,y,z); 
	}
	E.HPFA(s);
	for(i=1;i<n;++i)
	{
		printf("%lld ",dis[i]);
	}
	printf("%lld\n",dis[n]);
	return 0;
}