You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.

38 lines
936 B

#include <bits/stdc++.h>
using namespace std;
const int N = 1000010;
const int INF = 0x3f3f3f3f;
int g[150][150];
int w[N];
int main() {
int n;
cin >> n;
// 地图初始化
memset(g, 0x3f, sizeof g);
for (int i = 1; i <= n; i++) g[i][i] = 0;
for (int i = 1; i <= n; i++) {
int a, b;
cin >> w[i] >> a >> b;
if (a) g[i][a] = g[a][i] = 1; // 左链接,右链接,二叉树,和一般的不一样
if (b) g[i][b] = g[b][i] = 1;
}
// floyd
for (int k = 1; k <= n; k++)
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
if (g[i][j] > g[i][k] + g[k][j]) g[i][j] = g[i][k] + g[k][j];
int ans = INF;
for (int i = 1; i <= n; i++) {
int s = 0;
for (int j = 1; j <= n; j++) s += w[j] * g[i][j];
ans = min(ans, s);
}
printf("%d", ans);
return 0;
}