P1364 医院设置

#include<bits/stdc++.h>
using namespace std;
#define LL long long
const int N = 1e5 + 10;
int g[105][105];
int a[105];
int main() {
	int n;
	cin >> n;
	memset(g, 0x3f, sizeof g);
	for (int i = 1; i <= n; i++) {
		g[i][i] = 0;
		cin >> a[i];
		int u, v;
		cin >> u >> v;
		if (u > 0) g[i][u] = g[u][i] = 1;
		if (v > 0) g[i][v] = g[v][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]);
	int mn = 1e9;
	for (int i = 1; i <= n; i++) {
		int tot = 0;
		for (int j = 1; j <= n; j++)
			tot += g[i][j] * a[j];
		mn = min(mn, tot);
	}
	cout << mn;

	return 0;
}