RoseHeads.java

/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package senseofsecuritz;
 
import java.util.HashMap;
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;
 
/**
 *
 * @author istenik3
 */
public class RoseHeads {
    static int[][] cenyHran;
    static HashMap<Integer, Set<Integer>> edges;
 
    static public void main(String [] arguments) throws Exception {
        Scanner scanner = new Scanner(System.in);
 
        cenyHran = new int[1001][1001];
        edges = new HashMap<Integer, Set<Integer>>();
 
        while(scanner.hasNextInt()) {
            int nodes = scanner.nextInt();
            int startNode = scanner.nextInt();
 
            for(int i=1; i<=nodes; i++) {
                edges.put(i, new HashSet<Integer>());
            }
 
            // nacitame
            for(int i=0; i<nodes-1; i++) {
                int a = scanner.nextInt();
                int b = scanner.nextInt();
                int cena = scanner.nextInt();
                cenyHran[b][a] = cena;
                cenyHran[a][b] = cena;
                edges.get(b).add(a);
                edges.get(a).add(b);
            }
 
            int sucet = 0;
            //System.out.println(edges.get(startNode).size());
            for(int vrchol : edges.get(startNode)) {
 
                sucet += minCenaZaVypnutie(startNode, vrchol);
            }
 
            System.out.println(sucet);
        }
    }
 
    static public int minCenaZaVypnutie(int vrcholA, int vrcholB) {
        int najmensiaCena = cenyHran[vrcholA][vrcholB];
 
        int sucet = 0;
 
        if(edges.get(vrcholB).size() == 1) {
            return najmensiaCena;
        }
 
        for(int vrcholC : edges.get(vrcholB)) {
            if(vrcholC == vrcholA) {
                continue;
            }
            sucet += minCenaZaVypnutie(vrcholB, vrcholC);
        }
 
        return Math.min(najmensiaCena, sucet);
    }
}