记录编号	28751	评测结果	AAAAAAAAAA
题目名称	奶牛派对	最终得分	100
用户昵称	kaaala	是否通过	通过
代码语言	C++	运行时间	0.232 s
提交时间	2011-10-17 10:20:51	内存使用	4.14 MiB

#include<iostream>
#include<fstream>
#include<deque>

using namespace std;

const int oo=0x7fffffff;

struct node
{
	int v,w;
	node *next;
	node(int a,int b,node *c):v(a),w(b),next(c){}
}*adj[1006];

int n,m,x,ans,a[1006][1006];
bool f[1006];

void add(int a,int b,int t)
{
	adj[a]=new node(b,t,adj[a]);
}

void spfa(int s,int dis[])
{
	deque<int>q;
	int i;
	for(i=1;i<=n;i++)
		dis[i]=oo;
	q.push_back(s);
	f[s]=true;
	dis[s]=0;
	while(!q.empty())
	{
		int u=q.front();
		q.pop_front();
		f[u]=false;
		for(node *p=adj[u];p;p=p->next)
			if(dis[p->v]>dis[u]+p->w)
			{
				dis[p->v]=dis[u]+p->w;
				if(!f[p->v])
				{
					if(!q.empty()&&dis[p->v]>dis[q.front()])
						q.push_back(p->v);
					else
						q.push_front(p->v);
					f[p->v]=true;
				}
			}
	}
}

int main()
{
	int i,c,b,t;
	ifstream fin("party.in");
	ofstream fout("party.out");
	fin>>n>>m>>x;
	for(i=1;i<=m;i++)
	{
		fin>>c>>b>>t;
		add(c,b,t);
	}
	for(i=1;i<=n;i++)
		spfa(i,a[i]);
	for(i=1;i<=n;i++)
		if(a[i][x]+a[x][i]>ans)
			ans=a[i][x]+a[x][i];
	fout<<ans<<endl;
	fin.close();
	fout.close();
	return 0;
}