算法1

BFS

一开始当成了树，想用dfs做，没写出来，又仔细想了一下可以建图来做，是一个有权值有向图，并且无自环。

时间复杂度

$O(n^2)$

Java 代码

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        //Read console and build graph
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(reader.readLine());
        int[] population = new int[n + 1];
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i <= n; i++) {
            graph.add(new ArrayList<>());
        }

        for (int i = 1; i <= n; i++) {
            String[] str = reader.readLine().split(" ");
            population[i] = Integer.parseInt(str[0]);
            int u = Integer.parseInt(str[1]);
            int v = Integer.parseInt(str[2]);
            if (u != 0) {
                graph.get(i).add(u);
                graph.get(u).add(i);
            }
            if (v != 0) {
                graph.get(i).add(v);
                graph.get(v).add(i);
            }
        }
        reader.close();

        //BFS to get cost
        int minCost = Integer.MAX_VALUE;
        for (int i = 1; i <= n; i++) {
            Queue<Integer> q = new ArrayDeque<>();
            boolean[] visited = new boolean[n + 1];
            q.offer(i);
            int level = 0;
            int cost = 0;
            while (!q.isEmpty()) {
                int len = q.size();
                while (len-- > 0) {
                    int p = q.poll();
                    cost += level * population[p];
                    visited[p] = true;
                    for (int next : graph.get(p)) {
                        if (visited[next]) {
                            continue;
                        }
                        q.offer(next);
                    }
                }
                level++;
            }
            minCost = Math.min(minCost, cost);
        }

        //Print result
        System.out.println(minCost);
    }
}