比赛 20121030 评测结果 AAAAAAAAAA
题目名称 逃离遗迹 最终得分 100
用户昵称 Makazeu 运行时间 0.178 s
代码语言 C++ 内存使用 3.84 MiB
提交时间 2012-10-30 21:01:50
显示代码纯文本
#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;
}