记录编号	131259	评测结果	AAAAA
题目名称	医院设置	最终得分	100
用户昵称	乌龙猹	是否通过	通过
代码语言	C++	运行时间	0.004 s
提交时间	2014-10-24 08:21:28	内存使用	0.36 MiB

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
int n;
int x,y,tot;
int mi=0x7fffffff;//最大的数,进行比较 ;
int dis[110][110]={0};//任意两点距离; 
int sum[110];//各个结点人数； 
int main()
{
	freopen("hospital.in","r",stdin);
	freopen("hospital.out","w",stdout);
	cin>>n;
	for(int i=1;i<=n;++i)
	{
		for(int j=1;j<=n;++j)
		{
			dis[i][j]=100000;//先把所有的都认为最大 ;
		}
	}
	for(int i=1;i<=n;i++)
	{
		cin>>sum[i];
		dis[i][i]=0;//自己到自己距离为零； 
		cin>>x>>y;
		if(x) dis[i][x]=dis[x][i]=1;
		if(y) dis[i][y]=dis[y][i]=1;
	}
	for(int k=1;k<=n;k++)
	{
		for(int i=1;i<=n;i++)
		{
			if(k!=i)//不能以自己为中转点； 
			{
				for(int j=1;j<=n;j++)
				{
					if(i!=j&&k!=j&&dis[k][j]>dis[k][i]+dis[j][i])
					{
						dis[k][j]=dis[k][i]+dis[j][i];
					}
				}
			}
		}
	}
		for(int i=1;i<=n;++i)
	{
		tot=0;//距离和初始为0 ;
		for(int j=1;j<=n;++j)//分别枚举医院在每个点 ;
		{
			tot+=(sum[j]*dis[i][j]);//人数*最短距离为总距离 ;
		}
		if(tot<mi)//判断是否为最短的 
		{
			mi=tot;
		}
	}
	cout<<mi;
	return 0;
}