Source code for submission s889

Fr.java

  1.  
  2. import java.util.ArrayList;
  3. import java.util.LinkedList;
  4. import java.util.Scanner;
  5.  
  6. /*
  7.  * To change this template, choose Tools | Templates
  8.  * and open the template in the editor.
  9.  */
  10.  
  11.  
  12. /**
  13.  *
  14.  * @author cteam92
  15.  */
  16. public class Fr {
  17. static ArrayList <LinkedList<toEdge>> graph;
  18.  
  19. /**
  20.   * @param args the command line arguments
  21.   */
  22. public static void main(String[] args) {
  23. Scanner sc = new Scanner(System.in);
  24. while (true) {
  25. int n, c;
  26. int u, v, w;
  27.  
  28. if (!sc.hasNext()) break;
  29.  
  30. n = sc.nextInt();
  31. c = sc.nextInt();
  32.  
  33. graph = new ArrayList <LinkedList<toEdge>>();
  34. for (int i = 0; i < n; i++) {
  35. graph.add(new LinkedList<toEdge>());
  36. }
  37.  
  38. for (int i = 0; i < n - 1; i++) {
  39. u = sc.nextInt();
  40. v = sc.nextInt();
  41. w = sc.nextInt();
  42. sc.nextLine();
  43.  
  44. LinkedList<toEdge> vertex;
  45.  
  46. //System.out.println(u);
  47. //System.out.println(graph.);
  48. /*vertex = graph.get(u - 1);
  49.   toEdge V2 = new toEdge(v - 1, w);
  50.   vertex.add(V2);
  51.   graph.set(u - 1, vertex);*/
  52. graph.get(u-1).add(new toEdge(v-1, w));
  53. graph.get(v-1).add(new toEdge(u-1, w));
  54. }
  55.  
  56. //visited = new boolean[n];
  57. int sum = minOfEdges(c - 1, -1);
  58. System.out.println(sum);
  59. }
  60. }
  61.  
  62.  
  63. public static int minOfEdges(int node, int parent) {
  64. int sum = 0;
  65.  
  66. //System.out.println(node + " " + parent);
  67.  
  68. if (graph.get(node).size() == 1)
  69. return Integer.MAX_VALUE;
  70. for (toEdge e: graph.get(node)) {
  71. if (e.V != parent) {
  72. //System.out.println(e.value + ";" + minOfEdges(e.V, node));
  73. sum += Math.min(e.value, minOfEdges(e.V, node));
  74. }
  75. }
  76.  
  77. return sum;
  78. }
  79.  
  80. public static class toEdge {
  81. int V;
  82. int value;
  83.  
  84. public toEdge(int V, int value) {
  85. this.V = V;
  86. this.value = value;
  87. }
  88.  
  89. @Override
  90. public String toString() {
  91. return "toEdge{" + "V=" + V + ", value=" + value + '}';
  92. }
  93.  
  94.  
  95. }
  96. }
  97.