比赛 |
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;
}