Fr.java

/*
 * CTU Open 2013
 * HES
 */
package template;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;
import java.util.StringTokenizer;
 
/**
 *
 * @author cteam007
 */
public class Fr {
 
    StringTokenizer st = new StringTokenizer("");
    BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
 
    void useLine(String s) {
        st = new StringTokenizer(s);
    }
 
    String nextToken() throws Exception {
        while (!st.hasMoreTokens()) {
            st = new StringTokenizer(input.readLine());
        }
        return st.nextToken();
    }
 
    int nextInt() throws Exception {
        return Integer.parseInt(nextToken());
    }
 
    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) throws Exception {
        Fr instance = new Fr();
        while (instance.run()) {
        }
    }
 
    boolean run() throws Exception {
        String in = input.readLine();
        if (in == null) {
            return false;
        }
 
        useLine(in);
 
        int numberOfNodes = nextInt();
        int centralNode = nextInt();
 
        StartGraph sGraf = new StartGraph(numberOfNodes, centralNode);
 
        for (int i = 0; i < numberOfNodes - 1; i++) {
            int nodeOne = nextInt();
            int nodeTwo = nextInt();
            int valve = nextInt();
 
            sGraf.getStartNode(nodeOne).addEdge(nodeTwo, valve);
            sGraf.getStartNode(nodeTwo).addEdge(nodeOne, valve);
        }
 
        BFS.create(centralNode, sGraf);
 
        //System.out.println("");
        //sGraf.printGraph();
        //System.out.println("");
 
        System.out.println(sGraf.getStartNode(sGraf.central).minimum(sGraf));
 
        return true;
    }
}
 
class StartNode {
 
    int id;
    int parrent;
    int valve;
    char status;
    Map<Integer, Integer> neighbours = new HashMap<Integer, Integer>();
    Map<Integer, Integer> childs = new HashMap<Integer, Integer>();
 
    public StartNode(int id) {
        this.id = id;
        this.status = 'F';
        this.parrent = -1;
    }
 
    public void addEdge(int dest, int valve) {
        neighbours.put(dest, valve);
    }
 
    public void addChild(int dest, int valve) {
        childs.put(dest, valve);
    }
 
    public int minimum(StartGraph graph) {
 
        int min = 0;
        for (Integer integer : childs.keySet()) {
            StartNode v = graph.getStartNode(integer);
            min += v.minimum(graph);
        }
 
        if (childs.isEmpty()) {
            return valve;
        }
        return Math.min(min, valve);
    }
}
 
class StartGraph {
 
    Map<Integer, StartNode> nodes = new HashMap<Integer, StartNode>();
    int central;
    int count;
 
    public StartGraph(int count, int central) {
        this.central = central;
        this.count = count;
 
        for (int i = 1; i <= count; i++) {
            nodes.put(i, new StartNode(i));
        }
    }
 
    public StartNode getStartNode(int id) {
        return nodes.get(id);
    }
 
    public void printGraph() {
        for (int i = 0; i < count; i++) {
            System.out.println("Node: " + nodes.get(i).id + " v: " + nodes.get(i).valve);
 
            for (Integer integer : nodes.get(i).childs.keySet()) {
                StartNode v = getStartNode(integer);
                System.out.println("-->Node: " + v.id + " v: " + v.valve);
            }
        }
    }
}
 
class BFS {
 
    public static void create(int central, StartGraph graf) {
        StartNode s = graf.getStartNode(central);
 
        s.status = 'O';
        s.parrent = -1;
        s.valve = Integer.MAX_VALUE;
 
        Queue<Integer> queue = new LinkedList<Integer>();
 
        queue.add(central);
 
        while (!queue.isEmpty()) {
            StartNode u = graf.getStartNode(queue.remove());
 
 
            for (Integer integer : u.neighbours.keySet()) {
                StartNode v = graf.getStartNode(integer);
 
                if (v.status == 'F') {
                    u.addChild(v.id, u.neighbours.get(v.id));
                    v.valve = u.neighbours.get(v.id);
                    v.status = 'O';
                    v.parrent = u.id;
                    queue.add(v.id);
                }
            }
            u.status = 'C';
        }
    }
}