Source code for submission s921

FR.java

  1.  
  2. import java.io.BufferedReader;
  3. import java.io.IOException;
  4. import java.io.InputStreamReader;
  5. import java.util.ArrayList;
  6. import java.util.List;
  7.  
  8. /*
  9.  * To change this template, choose Tools | Templates
  10.  * and open the template in the editor.
  11.  */
  12. /**
  13.  *
  14.  * @author cteam94
  15.  */
  16. public class FR {
  17.  
  18. private List<List<Edge>> l;
  19.  
  20. public static void main(String[] args) throws IOException {
  21.  
  22. while ((new FR()).readLine(br));
  23. }
  24.  
  25. public boolean readLine(BufferedReader br) throws IOException {
  26. String line = br.readLine();
  27. if (line == null) {
  28. return false;
  29. }
  30.  
  31. String[] sp = line.split(" ");
  32. int n = Integer.parseInt(sp[0]);
  33. int root = Integer.parseInt(sp[1]);
  34. l = new ArrayList<List<Edge>>();
  35. for (int i = 0; i <= n; i++) {
  36. l.add(new ArrayList<Edge>());
  37. }
  38.  
  39. l.get(root).add(new Edge(root, -1, Integer.MAX_VALUE));
  40.  
  41. for (int i = 0; i < n - 1; i++) {
  42. String lnn = br.readLine();
  43. String[] ln = lnn.split(" ");
  44. int v1 = Integer.parseInt(ln[0]);
  45. int v2 = Integer.parseInt(ln[1]);
  46. int h = Integer.parseInt(ln[2]);
  47.  
  48. Edge e = new Edge(v1, v2, h);
  49.  
  50. l.get(v1).add(e);
  51. l.get(v2).add(e);
  52. }
  53.  
  54. // System.out.println("N = " + n + ", root=" + root);
  55. // System.out.println("List: " + l);
  56.  
  57. int x = w(root, -1);
  58. System.out.println(x);
  59.  
  60. return true;
  61. }
  62.  
  63. public int w(int u, int p) {
  64. List<Edge> v = l.get(u);
  65.  
  66. if (v.size() == 1) return v.get(0).h;
  67.  
  68. int c = 0;
  69. int c2 = Integer.MAX_VALUE;
  70. for (int i = 0; i < v.size(); i++) {
  71. Edge e = v.get(i);
  72. if (e.otherEnd(u) == p) {
  73. c2 = e.h;
  74. } else {
  75. c += w(e.otherEnd(u), u);
  76. }
  77. }
  78. return Math.min(c, c2);
  79. }
  80. }
  81.  
  82. class Edge {
  83.  
  84. public int v1;
  85. public int v2;
  86. public int h;
  87.  
  88. public Edge(int v1, int v2, int h) {
  89. this.v1 = v1;
  90. this.v2 = v2;
  91. this.h = h;
  92. }
  93.  
  94. public int otherEnd(int v) {
  95. if (v == v1) {
  96. return v2;
  97. }
  98. if (v == v2) {
  99. return v1;
  100. }
  101. return -1;
  102. }
  103. }
  104.