记录编号	165840	评测结果	AAAAAAAAAA
题目名称	[NOIP 2010冲刺十三]逃离遗迹	最终得分	100
用户昵称	神利·代目	是否通过	通过
代码语言	C++	运行时间	0.038 s
提交时间	2015-06-13 07:11:29	内存使用	2.28 MiB

#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
int temp,minl=2100000000,t,n,a,b,c,u,v,w,shu,first[22222],dis[22222],dd[22222];
queue<int>q;
bool p[22222];
char s;
struct bian
{
	int u,v,next,w;
}o[111111];
void add(int u,int v,int w)
{
	o[++shu].u=u;
	o[shu].v=v;
	o[shu].w=w;
	o[shu].next=first[u];
	first[u]=shu;
}
int in()
{
	temp=0;s=getchar();
	while(s<'0'||s>'9')
		s=getchar();
	for(;s>='0'&&s<='9';s=getchar())
		temp=temp*10+s-48;
	return temp;
}
int main()
{
	freopen("escapeb.in","r",stdin);
	freopen("escapeb.out","w",stdout);
	n=in();
	a=in();
	b=in();
	c=in();
	for(int i=1;i<n;i++)
	{
		u=in();
		v=in();
		w=in();
		add(u,v,w);
		add(v,u,w);
	}
//////////////////////////////////////////////////////////////////////
	memset(dis,0x3f,sizeof(dis));
	dis[a]=0;
	q.push(a);
	while(!q.empty())
	{
		u=q.front();
		for(int j=first[u];j;j=o[j].next)
		    if(dis[u]+o[j].w<dis[o[j].v])
		    {
				dis[o[j].v]=dis[u]+o[j].w;
				if(!p[o[j].v])
				{
					q.push(o[j].v);
					p[o[j].v]=1;
				}
		    }
		p[u]=0;
		q.pop();
	}
	for(int i=1;i<=n;i++)
	    dd[i]+=dis[i];
////////////////////////////////////////////////////////////////////////
	memset(dis,0x3f,sizeof(dis));
	dis[b]=0;
	q.push(b);
	while(!q.empty())
	{
		u=q.front();
		for(int j=first[u];j;j=o[j].next)
		    if(dis[u]+o[j].w<dis[o[j].v])
		    {
				dis[o[j].v]=dis[u]+o[j].w;
				if(!p[o[j].v])
				{
					q.push(o[j].v);
					p[o[j].v]=1;
				}
		    }
		p[u]=0;
		q.pop();
	}
	for(int i=1;i<=n;i++)
	    dd[i]+=dis[i];
////////////////////////////////////////////////////////////////////////
	memset(dis,0x3f,sizeof(dis));
	dis[c]=0;
	q.push(c);
	while(!q.empty())
	{
		u=q.front();
		for(int j=first[u];j;j=o[j].next)
		    if(dis[u]+o[j].w<dis[o[j].v])
		    {
				dis[o[j].v]=dis[u]+o[j].w;
				if(!p[o[j].v])
				{
					q.push(o[j].v);
					p[o[j].v]=1;
				}
		    }
		p[u]=0;
		q.pop();
	}
	for(int i=1;i<=n;i++)
	    dd[i]+=dis[i];
////////////////////////////////////////////////////////////////////////
	for(int i=1;i<=n;i++)
	    if(minl>dd[i])
	    {
			minl=dd[i];
			t=i;
	    }
	printf("%d\n%d",t,minl);
}