题目描述
设有一棵二叉树，如图：
其中，圈中的数字表示结点中居民的人口。圈边上数字表示结点编号，现在要求在某个结点上建立一个医院，使所有居民所走的路程之和为最小，同时约定，相邻接点之间的距离为 111。如上图中，若医院建在1 处，则距离和 =4+12+2×20+2×40=136=4+12+2\times20+2\times40=136=4+12+2×20+2×40=136；若医院建在 333 处，则距离和 =4×2+13+20+40=81=4\times2+13+20+40=81=4×2+13+20+40=81。 输入格式
第一行一个整数 nnn，表示树的结点数。
接下来的 nnn 行每行描述了一个结点的状况，包含三个整数 w,u,vw, u, vw,u,v，其中 www 为居民人口数，uuu 为左链接（为 000 表示无链接），vvv 为右链接（为 000 表示无链接）。 输出格式
一个整数，表示最小距离和。 输入输出样例 输入 #1
5 13 2 3 4 0 0 12 4 5 20 0 0 40 0 0
输出 #1
81
说明/提示 数据规模与约定
对于 10000% 的数据，保证 1≤n≤1001 \leq n \leq 1001≤n≤100，0≤u,v≤n0 \leq u, v \leq n0≤u,v≤n，1≤w≤1051 \leq w \leq 10^51≤w≤105。
#include <iostream> #include <algorithm> using namespace std; typedef long long ll; const int inf = 1e9; const int maxn = 130; int a[maxn]; int edge[maxn][maxn]; int n; int main() { cin >> n; fill(edge[0], edge[0] + maxn * maxn, inf); for(int i = 1; i <= n; i++) { edge[i][i] = 0; int l, r; cin >> a[i] >> l >> r; edge[i][l] = edge[l][i] = 1; edge[i][r] = edge[r][i] = 1; } for(int k = 1; k <= n; k++) { for(int i = 1; i <= n; i++) { for(int j = 1; j <= n; j++) { edge[i][j] = min(edge[i][j], edge[i][k] + edge[k][j]); } } } int ans = inf; for(int i = 1; i <= n; i++) { int tem = 0; for(int j = 1; j <= n; j++) tem += edge[j][i] * a[j]; ans = min(ans, tem); } cout << ans << endl; return 0; }