记录编号	9968	评测结果	AAAAA
题目名称	医院设置	最终得分	100
用户昵称	BYVoid	是否通过	通过
代码语言	C++	运行时间	0.003 s
提交时间	2009-04-23 11:45:19	内存使用	1.26 MiB

/* 
 * Problem: HAOI2009 模拟3 hospital
 * Author: Guo Jiabao
 * Time: 2009.4.23 8:48
 * State: Done
 * Memo: 无权图最短路径
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
const int MAXN=101,MAXM=MAXN*4;
using namespace std;
struct edge
{
	edge *next;
	int t;
}ES[MAXM],*V[MAXN];
int N,W[MAXN],EC,Ans=0x7FFFFFFF;
int dist[MAXN],Q[MAXN];
inline void addedge(int a,int b)
{
	ES[++EC].next=V[a];
	V[a]=ES+EC; V[a]->t=b;
}
void init()
{
	int i,w,a,b;
	freopen("hospital.in","r",stdin);
	freopen("hospital.out","w",stdout);
	scanf("%d",&N);
	for (i=1;i<=N;i++)
	{
		scanf("%d%d%d",&w,&a,&b);
		W[i]=w;
		if (a) addedge(i,a); addedge(a,i);
		if (b) addedge(i,b); addedge(b,i);
	}
}
void BFS(int S)
{
	int i,j,head=0,tail=-1;
	memset(dist,-1,sizeof(dist));
	dist[S]=0;
	Q[++tail]=S;
	while (head<=tail)
	{
		i=Q[head++];
		for (edge *e=V[i];e;e=e->next)
		{
			j=e->t;
			if (dist[j]==-1)
			{
				dist[j] = dist[i] + 1;
				Q[++tail] = j;
			}
		}
	}
}
void solve()
{
	int i,j,cost;
	for (i=1;i<=N;i++)
	{
		BFS(i);
		cost=0;
		for (j=1;j<=N;j++)
			cost += dist[j] * W[j];
		if (cost < Ans)
			Ans = cost;
	}
}
int main()
{
	init();
	solve();
	printf("%d\n",Ans);
	return 0;
}