比赛 |
20121030 |
评测结果 |
AAAAAAAAAA |
题目名称 |
逃离遗迹 |
最终得分 |
100 |
用户昵称 |
Truth.Cirno |
运行时间 |
0.278 s |
代码语言 |
C++ |
内存使用 |
3.54 MiB |
提交时间 |
2012-10-30 21:47:00 |
显示代码纯文本
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <vector>
using namespace std;
int waynum[20010],f[3][20010];
vector<int> wayto[20010],waycost[20010];
bool used[20010];
void dfs(int pos,int which,int costnow)
{
f[which][pos]=costnow;
int i,to,cost;
for (i=0;i<waynum[pos];i++)
{
to=wayto[pos][i];
if (!used[to])
{
cost=waycost[pos][i];
used[to]=true;
dfs(to,which,costnow+cost);
used[to]=false;
}
}
}
int main(void)
{
freopen("escapeb.in","r",stdin);
freopen("escapeb.out","w",stdout);
int i,n,a,b,c,u,v,w,mincost=~0u>>1,minpos=0,temp;
cin>>n>>a>>b>>c;
for (i=1;i<n;i++)
{
cin>>u>>v>>w;
waynum[u]++;
waynum[v]++;
wayto[u].push_back(v);
wayto[v].push_back(u);
waycost[u].push_back(w);
waycost[v].push_back(w);
}
used[a]=true;
dfs(a,0,0);
used[a]=false;
used[b]=true;
dfs(b,1,0);
used[b]=false;
used[c]=true;
dfs(c,2,0);
used[c]=false;
for (i=1;i<=n;i++)
{
temp=f[0][i]+f[1][i]+f[2][i];
if (mincost>temp)
{
mincost=temp;
minpos=i;
}
}
cout<<minpos<<endl<<mincost<<endl;
return(0);
}