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

#include<cstdio>
#include<cstring>
#include<queue>

using namespace std;
struct lentha
{
	int q,lenth;
    friend bool operator<(lentha a, lentha b)
	{
		return a.lenth > b.lenth;
		
	}
};


struct eda
{
	int be,en,val,next;
}c[50000];
lentha cc;
int a[50000],dis[50000],r[50000],A,B,C,out=0x7fffffff,ans;
int ppa[50000],ppb[50000],ppc[50000];
bool v[50000];
int n,jishuqi = 0,p;

void add(int x,int y, int z)
{
	c[++jishuqi].be = x;
	c[jishuqi].en = y;
	c[jishuqi].val = z;
	c[jishuqi].next = r[x];
	r[x] = jishuqi;
}
priority_queue<lentha> Q;
int DP(int st)
{
	int x,y;
	cc.q = st;
	cc.lenth = 0;
	Q.push(cc);
	memset(dis,70,sizeof(dis));
	memset(v,0,sizeof(v));
	dis[st] = 0;
	while (! Q.empty())
	{
		x = Q.top().q;
		y = Q.top().lenth;
		Q.pop(); 
		if (! v[x])
		{
			v[x] = true;
			for (int i = r[x]; i ; i = c[i].next)
			{
				cc.q = c[i].en;
				if (dis[cc.q]> y+c[i].val)
				{
				   dis[cc.q] = y+c[i].val;
				   cc.lenth = dis[cc.q];
				   Q.push(cc);
				}
			}
		}
	}
} 

int main()
{
	freopen("escapeb.in","r",stdin);
	freopen("escapeb.out","w",stdout);
	scanf("%d%d%d%d",&n,&A,&B,&C);
	int x,y,z;
	for (int i=1; i<=n-1; i++)
	{
		scanf("%d%d%d",&x,&y,&z);
		add(x,y,z);
		add(y,x,z);
	}
	int nali=0;
	DP(A);
	for(int i=1;i<=n;i++)//cout<<dis[i]<<" ";
//	cout<<endl;
	ppa[i]=dis[i];
	DP(B);
	for(int i=1;i<=n;i++)//cout<<dis[i]<<" ";cout<<endl;
	ppb[i]=dis[i];
	DP(C);
	for(int i=1;i<=n;i++)//cout<<dis[i]<<" ";cout<<endl;
	ppc[i]=dis[i];
	for(int i=1;i<=n;i++)
	{
		if(out>ppa[i]+ppb[i]+ppc[i])
		{
			out=ppa[i]+ppb[i]+ppc[i];
			nali=i;
		}
	}
    printf("%d\n%d",nali,out);
    //while(1);
    return 0;
}