记录编号	47177	评测结果	AAAAAAAAAA
题目名称	1241.[NOIP 2010冲刺十三]逃离遗迹	最终得分	100
用户昵称	TBK	是否通过	通过
代码语言	C++	运行时间	0.190 s
提交时间	2012-10-31 08:52:40	内存使用	4.08 MiB

#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;
}