Source code for submission s908

fr.java

  1. import java.io.BufferedReader;
  2. import java.io.IOException;
  3. import java.io.InputStreamReader;
  4. import java.util.ArrayList;
  5. import java.util.Arrays;
  6. import java.util.HashMap;
  7. import java.util.List;
  8. import java.util.Map;
  9. import java.util.regex.Pattern;
  10.  
  11. public class fr {
  12. private static class Hrana {
  13. public Hrana(int kam, int cena) {
  14. this.kam = kam;
  15. this.cena = cena;
  16. }
  17.  
  18. int kam;
  19. int cena;
  20.  
  21. @Override
  22. public String toString() {
  23. return "H[" + kam + ", " + cena + "]";
  24. }
  25.  
  26. }
  27.  
  28. private static class Cesta {
  29. Uzol u;
  30. int cena;
  31. }
  32.  
  33. private static class Uzol {
  34. public int id;
  35. public int idOtec;
  36. public int cenaknam;
  37. public Uzol(int c) {
  38. id = c;
  39. deti = new ArrayList<Cesta>();
  40. }
  41.  
  42. List<Cesta> deti;
  43.  
  44. public void vytvor() {
  45.  
  46. }
  47.  
  48. public void vytvor(Map<Integer, List<Hrana>> map,int cenaKNAM) {
  49. List<Hrana> list = map.get(id);
  50. cenaknam=cenaKNAM;
  51. for (Hrana hrana : list) {
  52. if (hrana.kam != idOtec) {
  53. Uzol syn = new Uzol(hrana.kam);
  54. syn.idOtec = id;
  55. Cesta cesta = new Cesta();
  56. cesta.cena = hrana.cena;
  57. cesta.u = syn;
  58. deti.add(cesta);
  59. syn.vytvor(map, hrana.cena);
  60. }
  61.  
  62. }
  63.  
  64. }
  65.  
  66. void vypis(int i) {
  67. String medzery = "";
  68. for (int j = 0; j < i; j++) {
  69. medzery += " ";
  70. }
  71. System.out.println(medzery + id);
  72. for (Cesta c : deti) {
  73. c.u.vypis(i + 1);
  74. }
  75.  
  76. }
  77.  
  78. int vypocet() {
  79. if(deti.size()==0){
  80. return cenaknam;
  81. }
  82. int cenadeti=0;
  83.  
  84. for (Cesta c : deti) {
  85. cenadeti+=c.u.vypocet();
  86. }
  87. // System.out.println("uzol:" + id+" cenaknam"+cenaknam+ " cenaDeti "+ cenadeti);
  88.  
  89. return Math.min(cenaknam, cenadeti);
  90. }
  91. }
  92.  
  93. public static void main(String[] args) throws IOException {
  94. Pattern p = Pattern.compile("\\s");
  95. String line;
  96. while ((line = buf.readLine()) != null) {
  97. String[] vstup = p.split(line);
  98. int n = Integer.parseInt(vstup[0]);
  99. int c = Integer.parseInt(vstup[1]);
  100. Map<Integer, List<Hrana>> map = new HashMap<Integer, List<Hrana>>();
  101. for (int i = 1; i < n; i++) {
  102. line = buf.readLine();
  103. vstup = p.split(line);
  104. int odkial = Integer.parseInt(vstup[0]);
  105. int kam = Integer.parseInt(vstup[1]);
  106. int cena = Integer.parseInt(vstup[2]);
  107. Hrana hrana = new Hrana(kam, cena);
  108. List<Hrana> list = map.get(odkial);
  109. if (list != null) {
  110. list.add(hrana);
  111. } else {
  112. List<Hrana> novyList = new ArrayList<Hrana>();
  113. novyList.add(hrana);
  114. map.put(odkial, novyList);
  115. }
  116.  
  117. Hrana hranaNaopak = new Hrana(odkial, cena);
  118. List<Hrana> list2 = map.get(kam);
  119. if (list2 != null) {
  120. list2.add(hranaNaopak);
  121. } else {
  122. List<Hrana> novyList = new ArrayList<Hrana>();
  123. novyList.add(hranaNaopak);
  124. map.put(kam, novyList);
  125. }
  126. }
  127. // System.out.println(map.get(1));
  128. Uzol koren = new Uzol(c);
  129. koren.vytvor(map,Integer.MAX_VALUE);
  130.  
  131. System.out.println(koren.vypocet());
  132. }
  133. }
  134.  
  135. }
  136.