BZOJ1631Usaco2007Feb.CowParty

#include
#include
#include
#define N (2010)
#define M (200010)
#define rg register
#define fa (x>>1)
using namespace std;
int n,m,x,tot,ans,dis[N],last[N],pos[N],sum[N];
struct edge{
	int to,pre,dis;
}e[M];
struct heap{
	int to,dis;
}h[N];
struct record{
	int u,v,dis;
}rec[M];
inline int read(){
	int k=0,f=1; char c=getchar();
	while(c<‘0‘||c>‘9‘)c==‘-‘&&(f=-1),c=getchar();
	while(‘0‘<=c&&c<=‘9‘)k=k*10+c-‘0‘,c=getchar();
	return k*f;
}
inline void add(int x,int y,int z){e[++tot]=(edge){y,last[x],z}; last[x]=tot;}
inline void up(int x){
	while(x>1&&h[fa].dis>h[x].dis){
		swap(h[fa],h[x]); swap(pos[h[fa].to],pos[h[x].to]);
		x=fa;
	}
}
inline void down(int x){
	while(x<=(tot>>1)){
		int son=x<<1;
		if(sonh[son+1].dis) son++;
		if(h[son].disdis[now]+e[i].dis){
			dis[to]=dis[now]+e[i].dis;
			if(!pos[to]) h[pos[to]=++tot]=(heap){to,dis[to]};
			up(pos[to]);
		}
		pos[now]=0;
	}
}
inline void clear(){
	memset(last,0,sizeof(last));
	memset(dis,32,sizeof(dis));
	memset(pos,0,sizeof(pos));
	tot=0;
}
void out(){
	for(int i=1;i<=n;i++) printf("%d ",dis[i]); puts("");
}
int main(){
	n=read(); m=read(); x=read();
	clear();
	for(rg int i=1;i<=m;i++){
		rec[i].u=read(); rec[i].v=read();
		add(rec[i].u,rec[i].v,rec[i].dis=read());
	}
	dijkstra(x); //out();
	for(int i=1;i<=n;i++) sum[i]=dis[i];
	clear();
	for(rg int i=1;i<=m;i++) add(rec[i].v,rec[i].u,rec[i].dis);
	dijkstra(x); //out();
	for(int i=1;i<=n;i++) ans=max(ans,sum[i]+dis[i]);
	printf("%d\n",ans);
	return 0;
}