记录编号	21489	评测结果	AAAAAAAAAA
题目名称	奶牛派对	最终得分	100
用户昵称	郭乾乐	是否通过	通过
代码语言	C++	运行时间	0.087 s
提交时间	2010-11-11 08:12:55	内存使用	7.91 MiB

#include<iostream>
#include<fstream>
using namespace std;

int a[1001][1001][2],n,m,e,maxn=99999999,b[1001][2];
void djs(int sn,int x)
{
	int i,j,wm,k,d[1001];
	bool t[1001];
	for(i=1;i<=n;i++)
	{
		d[i]=maxn;
		t[i]=true;
	}
	d[sn]=0;
	for(i=1;i<n;i++)
	{
		wm=maxn;
		for(j=1;j<=n;j++)
			if(t[j]&&d[j]<wm)
			{
				k=j;
				wm=d[j];
			}
		t[k]=false;
		for(j=1;j<=n;j++)
			if(t[j]&&(a[k][j][x]+d[k])<d[j])
				d[j]=a[k][j][x]+d[k];
	}
	for(i=1;i<=n;i++)
		b[i][x]=d[i];
}
int main()
{
	ifstream fin("party.in");
	ofstream fout("party.out");
	int i,x,y,j,mm=0;
	fin>>n>>m>>e;
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++)
		{
			a[i][j][0]=maxn;
			a[i][j][1]=maxn;
		}
	for(i=1;i<=m;i++)
	{
		fin>>x>>y;
		fin>>a[x][y][0];
		a[y][x][1]=a[x][y][0];
	}
	djs(e,0);
	djs(e,1);
	for(i=1;i<=n;i++)
		if((b[i][0]+b[i][1])>mm)
			mm=b[i][0]+b[i][1];
	fout<<mm<<endl;
	return 0;
}