比赛 20121030 评测结果 AAAAAAAAAA
题目名称 逃离遗迹 最终得分 100
用户昵称 feng 运行时间 0.060 s
代码语言 C++ 内存使用 3.60 MiB
提交时间 2012-10-30 20:40:30
显示代码纯文本
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<iostream>
using namespace std;
struct node{
	int s,nex;
}a[20010];
struct edge{
	int y,v,nex;
}e[40010];
bool f[20010];
int f1[20010];
int f2[20010];
int f3[20010];
int n,x,m,y,v,aa,bb,cc;
void dfs(int s){
	int i,tmp;
	tmp=a[s].nex;
	for (i=1;i<=a[s].s;i++){
		if (f[e[tmp].y]){
			f1[e[tmp].y]=f1[s]+e[tmp].v;
			f[e[tmp].y]=false;
			dfs(e[tmp].y);
		}
		tmp=e[tmp].nex;
	}
}
void add(int x,int y,int v){
	m++;
	a[x].s++;
	e[m].y=y;
	e[m].nex=a[x].nex;
	e[m].v=v;
	a[x].nex=m;
}
int main()
{
	freopen("escapeb.in","r",stdin);
	freopen("escapeb.out","w",stdout);
	scanf("%d%d%d%d",&n,&aa,&bb,&cc);
	m=0;
	for (int i=1;i<n;i++){
		scanf("%d%d%d",&x,&y,&v);
		add(x,y,v);
		add(y,x,v);
	}
	memset(f1,0,sizeof(f1));
	memset(f,true,sizeof(f));
	f[cc]=false;
	dfs(cc);
	for (int i=1;i<=n;i++)
		f3[i]=f1[i];
	memset(f1,0,sizeof(f1));
	memset(f,true,sizeof(f));
	f[bb]=false;
	dfs(bb);
	for (int i=1;i<=n;i++)
		f2[i]=f1[i];
	memset(f1,0,sizeof(f1));
	memset(f,true,sizeof(f));
	f[aa]=false;
	dfs(aa);
	int minn=2000000;
	int ans=0;
	for (int i=1;i<=n;i++){
		int tmp=f1[i]+f2[i]+f3[i];
		if (tmp<minn){
			minn=tmp;
			ans=i;
		}
	}
	printf("%d\n%d",ans,minn);
	return 0;
}