Source code for submission s831

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 = new int[1001][1000];
  11.     protected int[][] edgesPrice = new int[1001][1000];
  12.     protected int[] edgesCnt = new int[1001];
  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.             for (int i = 1; i <= nodesCnt; i++) {
  25.                 edgesCnt[i] = 0;
  26.             }
  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 s806

Main.java

--- c5.s806.cteam001.fr.java.0.Main.java
+++ c5.s831.cteam001.fr.java.0.Main.java
@@ -8,7 +8,7 @@
     protected int nodesCnt;
     protected int centralNode;
-    protected int[][] edges;
-    protected int[][] edgesPrice;
-    protected int[] edgesCnt;
+    protected int[][] edges = new int[1001][1000];
+    protected int[][] edgesPrice = new int[1001][1000];
+    protected int[] edgesCnt = new int[1001];
     
     public static void main(String[] args) throws Exception {
@@ -22,7 +22,7 @@
             this.centralNode = this.nextInt();
             
-            edges = new int[nodesCnt + 1][nodesCnt];
-            edgesPrice = new int[nodesCnt + 1][nodesCnt];
-            edgesCnt = new int[nodesCnt + 1];
+            for (int i = 1; i <= nodesCnt; i++) {
+                edgesCnt[i] = 0;
+            }
             
             for (int i = 0; i < this.nodesCnt - 1; i++) {