记录编号	334373	评测结果	AAAAAAAAAA
题目名称	奶牛派对	最终得分	100
用户昵称	Marvolo	是否通过	通过
代码语言	C++	运行时间	0.443 s
提交时间	2016-10-31 21:35:24	内存使用	5.49 MiB

#include<cstdio>
#include<iostream>
#include<cstring>
#define N 1010
#define INF 0x3f3f3f3f
using namespace std;
 
int n,m,i,zd,x,y,l,lsum=1,ans=0,t,w,j;
int head[N],dis[N],v[N],z[N];
struct line{
	int t,l,next;
}e[N*100];
 
namespace IO{
	char buf[1<<22],*fs,*ft;
	inline char gc(){return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))?0:*fs++;}
	inline int gint(){
		int x=0,ch=gc();
		while(ch<'0'||ch>'9') ch=gc();
		while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+ch-'0',ch=gc();
		return x;
	}
}
using namespace IO;
 
inline void Add(int s,int t,int l){
	e[lsum].t=t;	e[lsum].l=l;
	e[lsum].next=head[s];	head[s]=lsum++;
}
inline void Swap(int &x,int &y){int t=x;	x=y;	y=t;}
inline int max(int a,int b){return (a>b)?a:b;}
 
inline int SPFA(int S,int T){
	int j=0,y=0;
	memset(z,0,sizeof(z));	memset(dis,INF,sizeof(dis));
	memset(v,0,sizeof(v));	dis[S]=0;	t=0;	w=0;
	z[++t]=S;	v[S]=1;
	while (w!=t){
		w=(w+1)%n;	x=z[w];	v[x]=0;
			for (j=head[x];j;j=e[j].next)
			if (dis[x]+e[j].l<dis[e[j].t])	{
				dis[e[j].t]=dis[x]+e[j].l;
				if (!v[e[j].t])	{
				t=(t+1)%n;	y=(w+1)%n;	z[t]=e[j].t;	v[e[j].t]=1;
				if (dis[e[j].t]<dis[z[y]])	z[t]=z[y],z[y]=e[j].t;
			}   //SLF
		}
	}
	return dis[T];
}
 
int main(){
	freopen("party.in","r",stdin);
	freopen("party.out","w",stdout);
	n=gint();	m=gint();	zd=gint();
	for (i=1;i<=m;i++){
		x=gint();	y=gint();	l=gint();
		Add(x,y,l);
	}
	for (i=1;i<=n;i++){
		if (i==zd)	continue;
		ans=max(ans,SPFA(i,zd)+SPFA(zd,i));
	}
	printf("%d\n",ans);
	return 0;
}