测试地址：☞
【题目描述】
设有一棵二叉树（如下图），其中圈中的数字表示结点中居民的人口，圈边上数字表示结点编号。现在要求在某个结点上建立一个医院，使所有居民所走的路程之和为最小，同时约定，相邻结点之间的距离为11。就本图而言，若医院建在 1 处，则距离和 = 4+12+2×20+2×40 = 136；若医院建在 3 处，则距离和 = 4×2+13+20+40 = 81……
【输入】
第一行一个整数 n，表示树的结点数（n ≤ 100）。接下来的 n 行每行描述了一个结点的状况，包含三个整数，整数之间用空格（一个或多个）分隔，其中：第一个数为居民人口数；第二个数为左链接，为 0 表示无链接；第三个数为右链接，为 0 表示无链接。
【输出】
一个整数，表示最小距离和。
【输入样例】
5 13 2 3 4 0 0 12 4 5 20 0 0 40 0 0【输出样例】
81【思路】
用二维数组存储树，如果两个结点有边相连，记为 1，否则记为极大值；之后，Floyed求出任意两结点之间的最短路径（核心代码三层循环）；最后两层循环遍历出医院建在哪个结点使得居民所走路程之和最小。
【AC代码】
#include<iostream> #include<cstring> using namespace std; const int maxn=0x3f3f3f3f; int a[101], g[101][101]; int main(){ int n, l, r, sum; int minn = maxn; cin >> n; memset(g, maxn, sizeof(g)); for(int i = 1; i <= n; i++){ g[i][i] = 0; cin >> a[i] >> l >> r; if(l != 0) g[i][l] = g[l][i] = 1; if(r != 0) g[i][r] = g[r][i] = 1; } for(int k = 1; k <= n; k++){ for(int i = 1; i <= n; i++){ for(int j = 1; j <= n; j++){ g[i][j] = min(g[i][j], g[i][k]+g[k][j]); } } } for(int i = 1; i <= n; i++){ sum = 0; for(int j = 1; j <= n; j++){ sum += g[i][j]*a[j]; } minn = min(minn, sum); } cout << minn; return 0; }
