Source code for submission s956

Fr.java

  1. import java.util.*;
  2. import java.io.*;
  3.  
  4. public class Fr
  5. {
  6. public static HashMap<String, Node> nodes = new HashMap<String, Node>();
  7.  
  8. public static class Node
  9. {
  10. public ArrayList<Edge> edges;
  11.  
  12. public Node()
  13. {
  14. edges = new ArrayList<Edge>();
  15. }
  16.  
  17. public int minCost() {return minCost(null);}
  18. public int minCost(Edge parent)
  19. {
  20. if (edges.size() == 1)
  21. {
  22. return edges.get(0).cost;
  23. }
  24.  
  25. int sum = 0;
  26. for (Edge e : edges)
  27. {
  28. if (parent == null || !e.equals(parent))
  29. sum += e.getOther(this).minCost(e);
  30. }
  31. if (parent == null)
  32. return sum;
  33. if (parent.cost < sum)
  34. return parent.cost;
  35. return sum;
  36. }
  37. }
  38.  
  39. public static class Edge
  40. {
  41. public Node n1;
  42. public Node n2;
  43. public int cost;
  44. public Edge(Node n1, Node n2, int cost)
  45. {
  46. this.n1 = n1;
  47. this.n2 = n2;
  48. this.cost = cost;
  49. }
  50.  
  51. public Node getOther(Node me)
  52. {
  53. if (n1.equals(me))
  54. return n2;
  55. return n1;
  56. }
  57. }
  58.  
  59. public static void main(String[] args) throws Exception
  60. {
  61. while (true)
  62. {
  63. try
  64. {
  65. thing(in);
  66. }
  67. catch (Exception e)
  68. {
  69. break;
  70. }
  71. }
  72. }
  73.  
  74. public static void thing(BufferedReader in) throws Exception
  75. {
  76. String line = in.readLine();
  77. String[] splitline = line.split(" ");
  78. Integer n = Integer.valueOf(splitline[0]);
  79. String start = splitline[1];
  80. for (int i = 1; i <= n; i++)
  81. nodes.put(String.valueOf(i), new Node());
  82. for (int i = 0; i < n-1; i++)
  83. {
  84. line = in.readLine();
  85. splitline = line.split(" ");
  86. Node n1 = nodes.get(splitline[0]);
  87. Node n2 = nodes.get(splitline[1]);
  88. Edge e = new Edge(n1, n2, Integer.valueOf(splitline[2]));
  89. n1.edges.add(e);
  90. n2.edges.add(e);
  91. }
  92. System.out.println(nodes.get(start).minCost());
  93. }
  94. }