Source code for submission s806

Go to diff to previous submission

Main.java

  1.  
  2. import java.io.BufferedReader;
  3. import java.io.InputStreamReader;
  4. import java.util.StringTokenizer;
  5.  
  6. public class Main {
  7.  
  8.     protected int nodesCnt;
  9.     protected int centralNode;
  10.     protected int[][] edges;
  11.     protected int[][] edgesPrice;
  12.     protected int[] edgesCnt;
  13.  
  14.     public static void main(String[] args) throws Exception {
  15.         Main p = new Main();
  16.         p.run();
  17.     }
  18.  
  19.     protected void run() throws Exception {
  20.         while (input.ready()) {
  21.             this.nodesCnt = this.nextInt();
  22.             this.centralNode = this.nextInt();
  23.  
  24.             edges = new int[nodesCnt + 1][nodesCnt];
  25.             edgesPrice = new int[nodesCnt + 1][nodesCnt];
  26.             edgesCnt = new int[nodesCnt + 1];
  27.  
  28.             for (int i = 0; i < this.nodesCnt - 1; i++) {
  29.                 int b = this.nextInt();
  30.                 int e = this.nextInt();
  31.                 int price = this.nextInt();
  32.                 edges[b][edgesCnt[b]] = e;
  33.                 edges[e][edgesCnt[e]] = b;
  34.                 edgesPrice[b][edgesCnt[b]] = price;
  35.                 edgesPrice[e][edgesCnt[e]] = price;
  36.                 edgesCnt[b]++;
  37.                 edgesCnt[e]++;
  38.             }
  39.             System.out.println(getPrice(centralNode, -10, -10));
  40.         }
  41.     }
  42.  
  43.     protected int getPrice(int node, int parent, int parentPrice) {
  44.         if (edgesCnt[node] == 1 && parentPrice != -10) {
  45.             return edgesPrice[node][0];
  46.         }
  47.         int sum = 0;
  48.         for (int i = 0; i < edgesCnt[node]; i++) {
  49.             if (edges[node][i] != parent) {
  50.                 sum += getPrice(edges[node][i], node, edgesPrice[node][i]);
  51.             }
  52.             if (sum >= parentPrice && parentPrice != -10) {
  53.                 return parentPrice;
  54.             }
  55.         }
  56.         return sum;
  57.         /*int price = 0;
  58.         for (int i = 0; i < edgesCnt[node]; i++) {
  59.             if (edges[node][i] != parent) {
  60.                 closeMePrice += edgesPrice[node][i];
  61.                 closeChildrenPrice += getPrice(edges[node][i], node);
  62.             }
  63.         }
  64.         if (closeChildrenPrice == 0) {
  65.             return closeMePrice;
  66.         }
  67.         return Math.min(closeMePrice, closeChildrenPrice);*/
  68.     }
  69.  
  72.  
  73.     public String nextToken() throws Exception {
  74.         while (!st.hasMoreTokens()) {
  75.             st = new StringTokenizer(input.readLine());
  76.         }
  77.         return st.nextToken();
  78.     }
  79.  
  80.     public int nextInt() throws Exception {
  81.         return Integer.parseInt(nextToken());
  82.     }
  83.  
  84.     public String nextLine() throws Exception {
  85.         return input.readLine();
  86.     }
  87.  
  88. }
  89.  

Diff to submission s752

Main.java

--- c5.s752.cteam001.fr.java.0.Main.java
+++ c5.s806.cteam001.fr.java.0.Main.java
@@ -37,11 +37,23 @@
                 edgesCnt[e]++;
             }
-            System.out.println(getPrice(centralNode, -10));
+            System.out.println(getPrice(centralNode, -10, -10));
         }
     }
     
-    protected int getPrice(int node, int parent) {
-        int closeMePrice = 0;
-        int closeChildrenPrice = 0;
+    protected int getPrice(int node, int parent, int parentPrice) {
+        if (edgesCnt[node] == 1 && parentPrice != -10) {
+            return edgesPrice[node][0];
+        }
+        int sum = 0;
+        for (int i = 0; i < edgesCnt[node]; i++) {
+            if (edges[node][i] != parent) {
+                sum += getPrice(edges[node][i], node, edgesPrice[node][i]);
+            }
+            if (sum >= parentPrice && parentPrice != -10) {
+                return parentPrice;
+            }
+        }
+        return sum;
+        /*int price = 0;
         for (int i = 0; i < edgesCnt[node]; i++) {
             if (edges[node][i] != parent) {
@@ -53,5 +65,5 @@
             return closeMePrice;
         }
-        return Math.min(closeMePrice, closeChildrenPrice);
+        return Math.min(closeMePrice, closeChildrenPrice);*/
     }