记录编号	47143	评测结果	AAAAAAAAAA
题目名称	[NOIP 2010冲刺十三]逃离遗迹	最终得分	100
用户昵称	Makazeu	是否通过	通过
代码语言	C++	运行时间	0.178 s
提交时间	2012-10-30 22:24:53	内存使用	3.84 MiB

#include <cstdio>
#include <cstdlib>
#include <vector>
#include <cstring>
#include <string>
#include <algorithm>
using namespace std;
const int MAXN=20022;
int N,A,B,C,dist[3][MAXN]={0};
vector<int> map[MAXN],val[MAXN];

inline void init()
{
	int u,v,w;
	scanf("%d %d %d %d\n",&N,&A,&B,&C);
	for(int i=1;i<=N-1;i++)
	{
		scanf("%d %d %d\n",&u,&v,&w);
		map[u].push_back(v);val[u].push_back(w);
		map[v].push_back(u);val[v].push_back(w);
	}
}

void dfs(int k,int f,int d)
{
	int u;
	for(unsigned int i=0;i<map[k].size();i++)
	{
		u=map[k][i]; if(u==f) continue;
		dist[d][u]=dist[d][k]+val[k][i];
		dfs(u,k,d);
	}
}

int main()
{
	freopen("escapeb.in","r",stdin);
	freopen("escapeb.out","w",stdout);
	init();    dfs(A,0,0);
	dfs(B,0,1);dfs(C,0,2);
	int now=1,ans=20000*1000*3;
	for(int i=1;i<=N;i++)
	{
		if(dist[0][i]+dist[1][i]+dist[2][i]>=ans)continue;
		ans=dist[0][i]+dist[1][i]+dist[2][i]; now=i;
	}
	printf("%d\n%d\n",now,ans);
	return 0;
}