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
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;
|
|
} |