比赛 |
20121030 |
评测结果 |
AAAAAAAAAA |
题目名称 |
逃离遗迹 |
最终得分 |
100 |
用户昵称 |
TBK |
运行时间 |
0.189 s |
代码语言 |
C++ |
内存使用 |
4.08 MiB |
提交时间 |
2012-10-30 21:39:18 |
显示代码纯文本
#include <iostream>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <set>
#include <queue>
#include <algorithm>
#define MAXN 0x7fffffff
using namespace std;
vector <long long> v[20001][2];
long long a,b,c,d,l[20001],m[20001],n[20001],x,y,z,t,s;
bool bo[20001];
void DFS(int k)
{
int i;
for (i=0;i<v[k][0].size();i++)
if (bo[v[k][0][i]]==false)
{
l[v[k][0][i]]=l[k]+v[k][1][i];
bo[v[k][0][i]]=true;
DFS(v[k][0][i]);
}
}
void DFS1(int k)
{
int i;
for (i=0;i<v[k][0].size();i++)
if (bo[v[k][0][i]]==false)
{
m[v[k][0][i]]=m[k]+v[k][1][i];
bo[v[k][0][i]]=true;
DFS1(v[k][0][i]);
}
}
void DFS2(int k)
{
int i;
for (i=0;i<v[k][0].size();i++)
if (bo[v[k][0][i]]==false)
{
n[v[k][0][i]]=n[k]+v[k][1][i];
bo[v[k][0][i]]=true;
DFS2(v[k][0][i]);
}
}
int main(void)
{
freopen("escapeb.in","r",stdin);
freopen("escapeb.out","w",stdout);
scanf("%lld%lld%lld%lld",&b,&c,&d,&x);
for (y=0;y<b-1;y++)
{
scanf("%lld%lld%lld",&z,&t,&s);
v[z][0].push_back(t);
v[z][1].push_back(s);
v[t][0].push_back(z);
v[t][1].push_back(s);
}
bo[c]=true;
DFS(c);
memset(bo,0,sizeof(bo));
bo[d]=true;
DFS1(d);
memset(bo,0,sizeof(bo));
bo[x]=true;
DFS2(x);
t=MAXN;
for (y=1;y<=b;y++)
if (l[y]+m[y]+n[y]<t)
{
t=l[y]+m[y]+n[y];
s=y;
}
printf("%lld\n%lld",s,t);
fclose(stdin);
fclose(stdout);
return 0;
}