记录编号	134091	评测结果	AAAAAAAAAA
题目名称	聚会	最终得分	100
用户昵称	水中音	是否通过	通过
代码语言	C++	运行时间	0.017 s
提交时间	2014-10-29 13:52:35	内存使用	2.62 MiB

#include<iostream>
#include<cstdio>
using namespace std;
int qwq=0x7fffffff;
int to[100010]={0},ne[100010]={0},w[100010]={0},head[1001]={0},reto[100010]={0},rene[100010]={0},rehead[1001]={0},A[100000]={0},zui[1001]={0},rezui[1001]={0};
int j=0,k,i,p,m,n,zj1,zj2,zj3,ans=0;
void init()
{
	scanf("%d%d%d",&n,&m,&k);
	for(i=1;i<=m;i++)
	{
		scanf("%d%d%d",&zj1,&zj2,&zj3);
		j++;
		to[j]=zj2;
		ne[j]=head[zj1];
		head[zj1]=j;
		w[j]=zj3;
		reto[j]=zj1;
		rene[j]=rehead[zj2];
		rehead[zj2]=j;
	}
	for(i=1;i<=n;i++)
	{
		zui[i]=qwq;
		rezui[i]=zui[i];
	}
	zui[k]=0;
	rezui[k]=0;
}
void firstspfa()
{
	A[0]=1;
	A[1]=k;
	while(A[0])
	{
		zj1=A[ A[0] ];A[0]--;
		for(p=head[zj1];p;p=ne[p])
		{
			zj2=zui[zj1]+w[p];
			if(zui[ to[p] ]>zj2)
			{
				zui[ to[p] ]=zj2;
				A[0]++;
				A[ A[0] ]=to[p];
			}
		}
	}
}
void secondspfa()
{
	A[0]=1;
	A[1]=k;
	while(A[0])
	{
		zj1=A[ A[0] ];A[0]--;
		for(p=rehead[zj1];p;p=rene[p])
		{
			zj2=rezui[zj1]+w[p];
			if(rezui[ reto[p] ]>zj2)
			{
				rezui[ reto[p] ]=zj2;
				A[0]++;
				A[ A[0] ]=reto[p];
			}
		}
	}
}
int main()
{
	freopen("partyb.in","r",stdin);
	freopen("partyb.out","w",stdout);
	init();
	firstspfa();
	secondspfa();
	for(i=1;i<=n;i++)
	if(zui[i]!=qwq&&rezui[i]!=qwq)
	{
		zj1=zui[i]+rezui[i];
		if(zj1>ans)ans=zj1;
	}
	printf("%d\n",ans);
	return 0;
}