记录编号	134622	评测结果	AAAAAAAAAA
题目名称	奶牛派对	最终得分	100
用户昵称	乌龙猹	是否通过	通过
代码语言	C++	运行时间	0.004 s
提交时间	2014-10-30 16:23:23	内存使用	2.23 MiB

#include<queue>
#include<cstdio>
#include<cctype>
#include<cstring>
using namespace std;

int ret;
char ch;
int qin()
{
	ret=0;
	while(ch=getchar(),!isdigit(ch));
	while(ret=ret*10+ch-'0',ch=getchar(),isdigit(ch));
	return ret;
}

struct dx{
	int from,to;
	int next,nexus;
	int data;
};
dx jb[100001];
int last[1001];
int llast[1001];

int n,m,k;
int maxx=0;
int disk[1001];
int kdis[1001];

void spfa(int);
void ospfa(int);

int main()
{
	freopen("party.in","r",stdin);
	freopen("party.out","w",stdout);
	n=qin();m=qin();k=qin();
	for(int i=1;i<=m;i++)
	{
		int x,y,z;
		x=qin();y=qin();z=qin();

		jb[i].from=x;
		jb[i].nexus=llast[y];
		llast[y]=i;

		jb[i].to=y;
		jb[i].next=last[x];
		last[x]=i;

		jb[i].data=z;
	}
	spfa(k);
	ospfa(k);
	for(int i=1;i<=n;i++)
	{
		if(disk[i]==0x7f7f7f7f||kdis[i]==0x7f7f7f7f) continue;
		if(disk[i]+kdis[i]>maxx) maxx=disk[i]+kdis[i];
	}
	printf("%d\n",maxx);
	//while(1);
	fclose(stdin);
	fclose(stdout);
	return 0;
}
void spfa(int x)
{
	queue<int> q;
	bool flag[1001]={0};
	memset(disk,0x7f,sizeof(disk));
	disk[x]=0;
	q.push(x);
	flag[x]=1;
	while(!q.empty())
	{
		int k=q.front();
		int i=last[k];
		while(i)
		{
			int t=jb[i].to;
			if(disk[t]>disk[k]+jb[i].data)
			{
				disk[t]=disk[k]+jb[i].data;
				if(!flag[t])
				{
					q.push(t);
					flag[t]=1;
				}
			}
			i=jb[i].next;
		}
		flag[k]=0;
		q.pop();
	}
}
void ospfa(int x)
{
    queue<int> q;
	bool flag[1001]={0};
	memset(kdis,0x7f,sizeof(kdis));
	kdis[x]=0;
	q.push(x);
	flag[x]=1;
	while(!q.empty())
	{
		int k=q.front();
		int i=llast[k];
		while(i)
		{
			int t=jb[i].from;
			if(kdis[t]>kdis[k]+jb[i].data)
			{
				kdis[t]=kdis[k]+jb[i].data;
				if(!flag[t])
				{
					q.push(t);
					flag[t]=1;
				}
			}
			i=jb[i].nexus;
		}
		flag[k]=0;
		q.pop();
	}
}