记录编号	165661	评测结果	AAAAAAAAAA
题目名称	[NOIP 2010冲刺十三]逃离遗迹	最终得分	100
用户昵称	forever	是否通过	通过
代码语言	C++	运行时间	0.072 s
提交时间	2015-06-12 18:40:39	内存使用	1.15 MiB

#include<iostream>
#include<cstdlib>
#include<cstring>
#include<queue>
#include<cstdio>
using namespace std;
int n,dis[20006],a,b,c;
int head[20006],k,l,h;
int y[20006],r[20006],rr[20006];
struct jiege
{
	int hao;
	int juli;
	friend bool operator < (jiege a,jiege b)
	{
		return a.juli>b.juli;
	}
};
jiege fg;
struct dd
{
	int zhong;
	int juli;
	int next;
}jie[40010];
priority_queue<jiege>u;
int main()
{
	freopen("escapeb.in","r",stdin);
	freopen("escapeb.out","w",stdout);
	memset(head,-1,sizeof(head));
	scanf("%d %d %d %d",&n,&a,&b,&c);
	int minn=199999999,num;
	for(int i=1;i<=2*(n-1);++i)
	{
	   scanf("%d %d %d",&k,&l,&h);
	   jie[i].zhong=l;
	   jie[i].juli=h;
	   jie[i].next=head[k];
	   head[k]=i;
	   i++;
	   jie[i].zhong=k;
	   jie[i].juli=h;
	   jie[i].next=head[l];
	   head[l]=i;
	}
	    memset(dis,25,sizeof(dis));
		memset(y,0,sizeof(y));
		int tot=0;
		dis[a]=0;
		fg.hao=a;
		fg.juli=0;
		y[a]=1;
		u.push(fg);
		while(!u.empty())
		{
			int hu=u.top().hao;
			int hy=u.top().juli;
			u.pop();
			y[hu]=1;
			for(int k=head[hu];k!=-1;k=jie[k].next)
			{
				int hjy=jie[k].zhong;
				if(dis[hjy]>hy+jie[k].juli)
				{
					dis[hjy]=hy+jie[k].juli;
					fg.hao=hjy;
					fg.juli=dis[hjy];
					u.push(fg);
				}
			}
		}
		memset(r,25,sizeof(r));
		memset(y,0,sizeof(y));
		r[b]=0;
		fg.hao=b;
		fg.juli=0;
		y[b]=1;
		u.push(fg);
		while(!u.empty())
		{
			int hu=u.top().hao;
			int hy=u.top().juli;
			u.pop();
			y[hu]=1;
			for(int k=head[hu];k!=-1;k=jie[k].next)
			{
				int hjy=jie[k].zhong;
				if(r[hjy]>hy+jie[k].juli)
				{
					r[hjy]=hy+jie[k].juli;
					fg.hao=hjy;
					fg.juli=r[hjy];
					u.push(fg);
				}
			}
		}
		memset(rr,25,sizeof(rr));
		memset(y,0,sizeof(y));
		rr[c]=0;
		fg.hao=c;
		fg.juli=0;
		y[c]=1;
		u.push(fg);
		while(!u.empty())
		{
			int hu=u.top().hao;
			int hy=u.top().juli;
			u.pop();
			y[hu]=1;
			for(int k=head[hu];k!=-1;k=jie[k].next)
			{
				int hjy=jie[k].zhong;
				if(rr[hjy]>hy+jie[k].juli)
				{
					rr[hjy]=hy+jie[k].juli;
					fg.hao=hjy;
					fg.juli=rr[hjy];
					u.push(fg);
				}
			}
		}
	for(int i=1;i<=n;++i)
	  if(dis[i]+r[i]+rr[i]<minn)
	   {
			minn=dis[i]+r[i]+rr[i];
			num=i;
	   }
	printf("%d\n",num);
	printf("%d",minn);
	//system("pause");
}