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