Source code for submission s1015

Main.java

  1. package javafr;
  2.  
  3. import java.io.BufferedReader;
  4. import java.io.InputStreamReader;
  5. import java.util.ArrayDeque;
  6. import java.util.ArrayList;
  7. import java.util.Deque;
  8. import java.util.List;
  9. import java.util.PriorityQueue;
  10. import java.util.StringTokenizer;
  11.  
  12. public class Main {
  13.  
  14. static StringTokenizer st = new StringTokenizer("");
  15.  
  16. public static void main(String[] args) throws Exception {
  17.  
  18. try {
  19.  
  20. while (true) {
  21.  
  22. int vertices = Integer.parseInt(nextToken());
  23. int root = Integer.parseInt(nextToken());
  24.  
  25. int u, v, cost;
  26. List<List<Integer>> neigh = new ArrayList<List<Integer>>(vertices + 1);
  27.  
  28. List<Node> nodes = new ArrayList<Node>();
  29. for (int i = 0; i <= vertices; i++) {
  30. nodes.add(new Node());
  31. }
  32.  
  33. for (int i = 0; i < vertices - 1; i++) {
  34. u = Integer.parseInt(nextToken());
  35. v = Integer.parseInt(nextToken());
  36. cost = Integer.parseInt(nextToken());
  37. nodes.get(u).children.add(nodes.get(v));
  38. nodes.get(v).children.add(nodes.get(u));
  39. nodes.get(u).edges.add(cost);
  40. nodes.get(v).edges.add(cost);
  41. }
  42.  
  43. for (Node n : nodes)
  44. n.ctr = n.children.size() - 1;
  45. nodes.get(root).ctr = nodes.get(root).children.size();
  46.  
  47. Deque<Node> queue = new ArrayDeque<Node>();
  48. queue.push(nodes.get(root));
  49. while (!queue.isEmpty()) {
  50. Node node = queue.pop();
  51. for (int i = 0; i < node.children.size(); i++) {
  52. Node child = node.children.get(i);
  53. child.parent = node;
  54. child.cost = node.edges.get(i);
  55. child.childrenCost = 0;
  56. int index = child.children.indexOf(node);
  57. child.children.remove(index);
  58. child.edges.remove(index);
  59. queue.push(child);
  60. }
  61. }
  62.  
  63. PriorityQueue<Node> pq = new PriorityQueue<Main.Node>();
  64. for (int i = 1; i < nodes.size(); i++) {
  65. if (nodes.get(i).children.size() == 0)
  66. nodes.get(i).childrenCost = nodes.get(i).cost;
  67. pq.add(nodes.get(i));
  68. }
  69.  
  70. while (!pq.isEmpty()) {
  71. Node n = pq.poll();
  72. if (n.childrenCost < n.cost)
  73. n.cost = n.childrenCost;
  74. if (n.parent != null) {
  75. n.parent.childrenCost += n.cost;
  76. n.parent.ctr--;
  77. pq.remove(n.parent);
  78. pq.add(n.parent);
  79. }
  80. }
  81.  
  82. System.out.println(nodes.get(root).childrenCost);
  83.  
  84. }
  85. } catch (Exception e) {
  86. // lol
  87. }
  88. }
  89.  
  90. static String nextToken() throws Exception {
  91. while (!st.hasMoreTokens()) {
  92. st = new StringTokenizer(input.readLine());
  93. }
  94. return st.nextToken();
  95. }
  96.  
  97. private static final class Node implements Comparable<Node> {
  98. Node parent;
  99. List<Node> children = new ArrayList<Node>();
  100. List<Integer> edges = new ArrayList<Integer>();
  101. int cost, childrenCost;
  102. int ctr;
  103.  
  104. public int compareTo(Node arg0) {
  105. return ctr - arg0.ctr;
  106. }
  107.  
  108.  
  109. }
  110.  
  111. }
  112.