Source code for submission s1039

Fr.java

  1.  
  2. import java.util.ArrayList;
  3. import java.util.HashMap;
  4. import java.util.List;
  5. import java.util.Map;
  6. import java.util.Scanner;
  7.  
  8. /*
  9.  * To change this template, choose Tools | Templates
  10.  * and open the template in the editor.
  11.  */
  12.  
  13. /**
  14.  *
  15.  * @author cteam038
  16.  */
  17. public class Fr {
  18.  
  19. static class Edge {
  20. public final int sNode;
  21. public final int dNode;
  22. public final int weight;
  23.  
  24. public Edge(int sNode, int dNode, int weight) {
  25. this.sNode = sNode;
  26. this.dNode = dNode;
  27. this.weight = weight;
  28. }
  29.  
  30. public String toString() {
  31. return sNode + " " + dNode;
  32. }
  33.  
  34. }
  35.  
  36. private static Map<Integer, List<Edge>> edges;
  37.  
  38. private static void addToMap(int node, Edge edge) {
  39. //System.out.println("add "+node+" edge "+edge);
  40. if (!edges.containsKey(node)) {
  41. edges.put(node, new ArrayList<Edge>());
  42. }
  43. edges.get(node).add(edge);
  44. }
  45.  
  46. private static int traverse(int node, int topWeight, Edge parent) {
  47. //System.out.println("node "+node);
  48. if (parent != null && edges.get(node).size() <= 1) {
  49. // sme na listu
  50. //System.out.println("return");
  51. return topWeight;
  52. }
  53. int downWeight = 0;
  54. for (Edge child : edges.get(node)) {
  55. //System.out.println("child "+child);
  56. if (child != parent) {
  57. int dNode = child.sNode == node ? child.dNode : child.sNode;
  58. // System.out.println("goto node "+dNode);
  59. downWeight += traverse(dNode, Math.min(topWeight,child.weight), child);
  60. // System.out.println("back from "+dNode);
  61. }
  62. }
  63. // System.out.println("returning (non-leaf)");
  64. return Math.min(downWeight, topWeight);
  65. }
  66.  
  67. public static void main(String [] args) {
  68. Scanner scanner = new Scanner(System.in);
  69. while (scanner.hasNext()) {
  70. edges = new HashMap<Integer, List<Edge>>();
  71. int nodes = scanner.nextInt();
  72. int central = scanner.nextInt();
  73. for (int i=0; i < nodes - 1; i++) {
  74. Edge edge = new Edge(scanner.nextInt(), scanner.nextInt(), scanner.nextInt());
  75. addToMap(edge.sNode, edge);
  76. addToMap(edge.dNode, edge);
  77. }
  78.  
  79. System.out.println(traverse(central, Integer.MAX_VALUE, null));
  80. }
  81. }
  82. }
  83.