记录编号	58338	评测结果	AAAAAAAAAA
题目名称	聚会	最终得分	100
用户昵称	苏轼	是否通过	通过
代码语言	C++	运行时间	0.021 s
提交时间	2013-04-19 15:18:26	内存使用	7.11 MiB

#include <fstream>
#include <deque>
using namespace std;
ifstream fi("partyb.in");
ofstream fo("partyb.out");
int n,m,k,g[1001][1001],d1[1001],d2[1001];
bool f[1001];
deque <int> v;
void init()
{
	int i,a,b,c,j;
	fi>>n>>m>>k;
	for (i=1;i<=n;i++)
		for (j=1;j<=n;j++) g[i][j]=-1;
	for (i=1;i<=n;i++) {f[i]=true;d1[i]=999999999;d2[i]=999999999;}d1[k]=0;d2[k]=0;
	for (i=1;i<=m;i++)
	{
		fi>>a>>b>>c;
		if (g[a][b]!=-1)
		{
			if (g[a][b]>c) g[a][b]=c;
		}else g[a][b]=c;
	}
}
bool relax1(int x,int y)
{
	if (d1[y]>d1[x]+g[x][y]) return true;return false;
}
void spfa1()
{
	int r,u;
	while (v.size())
	{
		u=v[0];v.pop_front();f[u]=true;
		for (r=1;r<=n;r++)
		{
			if (g[u][r]!=-1&&relax1(u,r))
			{
				d1[r]=d1[u]+g[u][r];v.push_back(r);f[r]=false;
			}
		}
	}
}
bool relax2(int x,int y)
{
	if (d2[y]>d2[x]+g[y][x]) return true;else return false;
}
void spfa2()
{
	int r,u;
	while (v.size())
	{
		u=v[0];v.pop_front();f[u]=true;
		for (r=1;r<=n;r++)
		{
			if (g[r][u]!=-1&&relax2(u,r))
			{
				d2[r]=d2[u]+g[r][u];v.push_back(r);f[r]=false;
			}
		}
	}
}
void out()
{
	int i,ans=-999999999;
	for (i=1;i<=n;i++)
		if (d1[i]!=999999999&&d2[i]!=999999999&&d1[i]+d2[i]>ans) ans=d1[i]+d2[i];
	fo<<ans<<endl;
}
int main()
{
	int i;
	init();
	v.push_back(k);
	spfa1();v.clear();
	for (i=1;i<=n;i++) f[i]=true;
	v.push_back(k);
	spfa2();
	out();
	return 0;
}