记录编号	221509	评测结果	AAAAAAAAAA
题目名称	奶牛派对	最终得分	100
用户昵称	liu_runda	是否通过	通过
代码语言	C++	运行时间	0.008 s
提交时间	2016-01-24 06:34:32	内存使用	2.61 MiB

#include<cstdio>
#include<queue>
using namespace std;
struct node{
	int dis;
	int v;
	node(int _dis,int _v){
		dis=_dis;v=_v;
	}
	bool operator < (const node &t)const{
		return dis>t.dis;
	}
};
int ans1[1005],ans2[1005],first1[1005],first2[1005];
struct edge{
	int next,w,to;
}lst1[100005],lst2[100005];
int len=1;
void insert(int v1,int v2,int cost){
	lst1[len].to = v2;
	lst1[len].next = first1[v1];
	lst1[len].w = cost;
	lst2[len].to = v1;
	lst2[len].next = first2[v2];
	lst2[len].w = cost;
	first1[v1]=first2[v2]=len++;
}
int n,m,x;
void dij(int ans[],int first[],edge lst[]){
	priority_queue <node> q;
	ans[x]=0;
	for(int pt = first[x];pt;pt = lst[pt].next){
		q.push(node(lst[pt].w,lst[pt].to));
	}
	while(!q.empty()){
		while(!q.empty()&&ans[q.top().v]!=0)q.pop();
		if(q.empty())break;
		ans[q.top().v] = q.top().dis;
		int vert = q.top().v;
		q.pop();
		for(int pt = first[vert];pt;pt=lst[pt].next){
			if(ans[lst[pt].to]==0&&lst[pt].to!=x)q.push(node(ans[vert]+lst[pt].w,lst[pt].to));
		}
	}
}
int main(){
	freopen("party.in","r",stdin);
	freopen("party.out","w",stdout);
	scanf("%d %d %d",&n,&m,&x);
	int a,b,c;
	for(int i = 0;i<m;++i){
		scanf("%d %d %d",&a,&b,&c);
		insert(a,b,c);
	}
	dij(ans1,first1,lst1);
	dij(ans2,first2,lst2);
	int maxdis = 0,nowdis;
	/*for(int i = 1;i<=n;++i)printf("%d ",ans1[i]);
	printf("\n");
	for(int i = 1;i<=n;++i)printf("%d ",ans2[i]);
	printf("\n");*/
	for(int i = 1;i<=n;++i){
		nowdis = ans1[i]+ans2[i];
		if(ans1[i]&&ans2[i]&&nowdis>maxdis)maxdis = nowdis;
	}
	printf("%d\n",maxdis);
	fclose(stdin);fclose(stdout);
	return 0;
}