1654: 医院设置
Time Limit: 1 Sec  Memory Limit: 65535 MB   64bit IO Format: %lld
Description
一颗二叉树有n（1≤n≤50）个结点，分别编号为1到n，每个结点代表一个居民点，每个居民点都有一定数量的居民（≤100）。现在需要选择一个居民点建一家医院，使得所有居民走的路程之和最小。同时约定，相邻两节点之间的距离为1。
例如对于样例，有5个居民点，每个居民点的居民数量分别为13，4，12，20，40.如果选择居民点1作为医院位置的话，则距离和为4*1+13*0+12*1+20*2+40*2=136；若选择居民点3的话，则距离和为4*2+13*1+12*0+20*1+40*1=81，…
Input
包含多组测试数据。每组测试数据第一行包含一个整数n，接下来的n行，每行3个数据，表示居民点i（1≤i≤n）的居民数和相邻两个居民点编号，如果编号为0表示不存在。
Output
输出最小距离和。
Sample Input  
 
5
13 2 3
4 0 0
12 4 5
20 0 0
40 0 0


Sample Output
81

中文题目，一般人都是用二叉树来做。

后来发现这道题目的数据范围很小，可以用Floyd算法求的任意两点间的距离，暴力一下就可以过。


#include<iostream>
#include<cstdio>
#include<cstring>
#include<functional>
#include<algorithm>
#define inf 0x3f3f3f3f
#define maxn 105
using namespace std;
int n,m,ans;
int maps[maxn][maxn];
int num[maxn];
void init()
{
	int i,j;
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++)
			if(i==j)
				maps[i][j]=0;
			else
				maps[i][j]=inf;
}
void floyd()
{
	int i,j,k;
	for(k=1;k<=n;k++)
		for(i=1;i<=n;i++)
			for(j=1;j<=n;j++)
				if(maps[i][j]>maps[i][k]+maps[k][j])
					maps[i][j]=maps[i][k]+maps[k][j];

int main()
{
	int i,j,a,b,c;
	while(scanf("%d",&n)!=EOF)
	{
		init();
		for(i=1;i<=n;i++)
		{
			scanf("%d%d%d",&a,&b,&c);
			num[i]=a;
			maps[i][b]=1;//无向图
			maps[b][i]=1;
			maps[i][c]=1;
			maps[c][i]=1;
		}
		floyd();//求任意两点间最短距离
		int sum;
		ans=inf;
		for(i=1;i<=n;i++)//暴力枚举下每一种情况
		{
			sum=0;
			for(j=1;j<=n;j++)
				sum+=(num[j]*maps[i][j]);
			ans=min(ans,sum);
		}
		printf("%d\n",ans);
	}
}