Fr.java

/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package basic;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
import java.util.StringTokenizer;
 
/**
 *
 * @author cteam043
 */
public class Fr {
 
    static final double EPS = 1E-7;
    Scanner sc = new Scanner(System.in);
    StringTokenizer st = new StringTokenizer("");
    BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
 
    String nextToken() throws Exception {
        while (!st.hasMoreTokens()) {
            st = new StringTokenizer(input.readLine());
        }
        return st.nextToken();
    }
 
    int nextInt() throws Exception {
        return Integer.parseInt(nextToken());
    }
    int[][] matrix = new int[1001][1001];
    int n, root;
 
    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) throws Exception {
        new Fr().solve();
    }
 
    public void solve() throws Exception {
        int u, v, w;
        while (sc.hasNextInt()) { // nextToken eof?
            n = sc.nextInt();
            root = sc.nextInt();
            for(int i = 0; i <= n; i++){
                for(int j = 0; j <= n; j++){
                    matrix[i][j] = 0;
                }
            }
            //System.out.println(n + " " + root);
            for (int i = 0; i < n - 1; i++) {
                u = sc.nextInt();
                v = sc.nextInt();
                w = sc.nextInt();
            //System.out.println(u + " " + v + " " + w);
                matrix[u][v] = matrix[v][u] = w;
            }
            int min = 0;
            for (int i = 1; i <= n; i++) {
                if (matrix[root][i] > 0) {
                    min += getMin(i, root);
                }
            }
            System.out.println(min);
        }
    }
 
    public int getMin(int node, int prev) {
        int min = 0;
        for (int i = 1; i <= n; i++) {
            if (matrix[node][i] > 0 && i != prev) {
                min += getMin(i, node);
            }
        }
        if(min == 0){
            return matrix[node][prev];
        } else {
            return Math.min(matrix[node][prev], min);
        }
    }
}