记录编号	58330	评测结果	AAAAAAAAAA
题目名称	聚会	最终得分	100
用户昵称	feng	是否通过	通过
代码语言	C++	运行时间	0.034 s
提交时间	2013-04-19 14:37:21	内存使用	8.21 MiB

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
using namespace std;
struct node{
	int nex;
	
}a[2200];
struct edge{
	int nex,y,v;
}e[220000];


int n,m,s,p;
int dis1[2200];
bool f[2200];
int x[220000];
int y[220000];
int v[220000];
int ans[2200];
int min(int a,int b){
	return a<b?a:b;
}
void init(){
	freopen("partyb.in","r",stdin);
	freopen("partyb.out","w",stdout);
	scanf("%d%d%d",&n,&m,&s);
	for (int i=1;i<=m;i++)
		scanf("%d%d%d",&x[i],&y[i],&v[i]);
}
void add(int x,int y,int v){
	p++;
	e[p].nex=a[x].nex;
	a[x].nex=p;
	e[p].y=y;
	e[p].v=v;
	
}
void dij1(int s){
	memset(dis1,10,sizeof(dis1));
	memset(f,false,sizeof(f));
	f[s]=true;
	dis1[s]=0;
	int t=a[s].nex;
	int y,v;
	while (t){
		y=e[t].y;
		v=e[t].v;
		dis1[y]=min(dis1[y],v);
		t=e[t].nex;
	}
	int k,minn;
	for (int i=2;i<=n;i++){
		minn=dis1[0];
		for (int j=1;j<=n;j++)
			if (!f[j] && dis1[j]<minn){
				
				minn=dis1[j];
				if (minn==0){
					int o;
					o++;
				}
				k=j;
			}
		f[k]=true;
		t=a[k].nex;
		while (t){
			y=e[t].y;
			v=e[t].v;
			if (!f[y])
				dis1[y]=min(dis1[y],v+dis1[k]);
			t=e[t].nex;
		}
	}
}
void work(){
	p=0;
	for (int i=1;i<=m;i++)
		add(x[i],y[i],v[i]);
	dij1(s);
	for (int i=1;i<=n;i++)
		ans[i]+=dis1[i];
	memset(a,0,sizeof(a));
	memset(e,0,sizeof(e));
	p=0;
	for (int i=1;i<=m;i++)
		add(y[i],x[i],v[i]);
	dij1(s);
	for (int i=1;i<=n;i++)
		ans[i]+=dis1[i];
	int maxx=0;
	for (int i=1;i<=n;i++)
		if (ans[i]>maxx && ans[i]<=dis1[0]) maxx=ans[i];
	printf("%d",maxx);
	
}


int main()
{
	init();
	work();
	return 0;
}