记录编号	264743	评测结果	AAAAAAAAAA
题目名称	[NOIP 2010冲刺十三]逃离遗迹	最终得分	100
用户昵称	Magic_Sheep	是否通过	通过
代码语言	C++	运行时间	0.028 s
提交时间	2016-05-30 16:28:46	内存使用	0.76 MiB

#include<cstdio>
#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
using namespace std;
const int maxn=20005;
vector<int> f[maxn];
vector<int> q[maxn];
bool vis[maxn];
queue<int> qu;
int dist1[maxn],dist2[maxn],dist3[maxn];
inline void get1(int &x)
{
	char ch;
	while(ch=getchar(),ch<48||ch>57);
	x=ch-48;
	while(ch=getchar(),ch>47&&ch<58)x=x*10+ch-48;
}
inline void spfa1(int x)
{
    memset(vis,false,sizeof(vis));
    memset(dist1,63,sizeof(dist1));
    dist1[x]=0;
    while(!qu.empty()) qu.pop();
    qu.push(x);
    vis[x]=true;
    while(!qu.empty())
    {
        int u=qu.front();
        qu.pop();
        for(int i=0;i<f[u].size();i++)
        {
            if(dist1[u]+1<dist1[f[u][i]])
            {
                dist1[f[u][i]]=dist1[u]+q[u][i];
                if(!vis[f[u][i]])
                {
                    vis[f[u][i]]=true;
                    qu.push(f[u][i]);
                }
            }
        }
        vis[u]=false;
    }
}
inline void spfa2(int x)
{
    memset(vis,false,sizeof(vis));
    memset(dist2,63,sizeof(dist2));
    dist2[x]=0;
    while(!qu.empty()) qu.pop();
    qu.push(x);
    vis[x]=true;
    while(!qu.empty())
    {
        int u=qu.front();
        qu.pop();
        for(int i=0;i<f[u].size();i++)
        {
            if(dist2[u]+1<dist2[f[u][i]])
            {
                dist2[f[u][i]]=dist2[u]+q[u][i];
                if(!vis[f[u][i]])
                {
                    vis[f[u][i]]=true;
                    qu.push(f[u][i]);
                }
            }
        }
        vis[u]=false;
    }
}
inline void spfa3(int x)
{
    memset(vis,false,sizeof(vis));
    memset(dist3,63,sizeof(dist3));
    dist3[x]=0;
    while(!qu.empty()) qu.pop();
    qu.push(x);
    vis[x]=true;
    while(!qu.empty())
    {
        int u=qu.front();
        qu.pop();
        for(int i=0;i<f[u].size();i++)
        {
            if(dist3[u]+1<dist3[f[u][i]])
            {
                dist3[f[u][i]]=dist3[u]+q[u][i];
                if(!vis[f[u][i]])
                {
                    vis[f[u][i]]=true;
                    qu.push(f[u][i]);
                }
            }
        }
        vis[u]=false;
    }
}
int MAIN()
{
    freopen("escapeb.in","r",stdin);
    freopen("escapeb.out","w",stdout);
    int n,a,b,c;
    get1(n);
    get1(a);
    get1(b);
    get1(c);
    int x,y,z;
    for(int i=1;i<n;i++)
    {
         get1(x);
         get1(y);
         get1(z);
         f[x].push_back(y);
         f[y].push_back(x);
         q[x].push_back(z);
         q[y].push_back(z);
    }
    spfa1(a);
    spfa2(b);
    spfa3(c);
    int minn=100000000;
    for(int i=1;i<=n;i++)
    {
         minn=min(minn,dist1[i]+dist2[i]+dist3[i]);
    }
    for(int i=1;i<=n;i++)
    {
        if(dist1[i]+dist2[i]+dist3[i]==minn)
        {
            printf("%d\n%d",i,minn);
            return 0;
        }
    }
    return 0;
}
int ezoi=MAIN();
int main(){;}