Go to diff to previous submission
import java.util.ArrayList; import java.util.Arrays; import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; import javax.management.Query; public class Fr { int n; int main; ArrayList<Node> nodes; int a; int b; int v; Node tempNode; Node father; while(sc.hasNextInt()){ a = 0; b = 0; n = sc.nextInt(); main = sc.nextInt(); nodes = null; nodes = new ArrayList<Node>(n+1); int[][] mat = new int[n+1][n+1]; for (int i = 0; i < n+1; i++) { nodes.add(new Node(i)); } for (int i = 0; i < n-1; i++) { a = sc.nextInt(); b = sc.nextInt(); v = sc.nextInt(); mat[a][b] = v; mat[b][a] = v; } Queue<Integer> q = new LinkedList<Integer>(); q.add(main); int[] used = new int[n+1]; int nodeID; used[main] = 1; // printMatrix(mat); while(!q.isEmpty()){ nodeID = q.poll(); for (int i = 1; i < n+1; i++) { if (used[i] == 0 && i != nodeID && mat[nodeID][i] != 0){ used[i] = 1; q.add(i); tempNode = nodes.get(i); tempNode.value = mat[nodeID][i]; nodes.get(nodeID).addChild(tempNode); // System.out.println(nodeID+" "+i); } } } // System.out.println(); // for (int i = 0; i < n+1; i++) { // nodes.add(new Node(i)); // } //// System.out.println(nodes.size()); // // nodes.get(main).setValue(Integer.MAX_VALUE); //// nodes.add(main, new Node(main, Integer.MAX_VALUE)); // // for (int i = 0; i < n-1; i++) { // a = sc.nextInt(); // b = sc.nextInt(); // v = sc.nextInt(); // // father = nodes.get(a); // if (father == null){ // tempNode = new Node(a, v); // nodes.set(a, tempNode); // // father = nodes.get(b); // father.addChild(tempNode); // }else{ // tempNode = new Node(b, v); // nodes.set(b, tempNode); // // father.addChild(tempNode); // } // } // // System.out.println(getNodeValue(nodes.get(main))); } sc.close(); } static void printMatrix(int[][]array){ for (int i = 0; i < array.length; i++) { } } static int getNodeValue(Node node){ if (node.child.size() == 0){ return node.value; } int sumV = 0; for (Node n : node.child) { sumV += getNodeValue(n); } if (node.value > sumV){ node.value = sumV; return node.value; } return node.value; } } class Node{ int id; int value; LinkedList<Node> child; Node ancestor; public Node(int id) { super(); this.id = id; child = new LinkedList<Node>(); // this.ancestor = ancestor; } void addChild(Node node){ this.child.add(node); } void setValue(int value){ this.value = value; } }
--- c5.s770.cteam055.fr.java.0.Fr.java +++ c5.s876.cteam055.fr.java.0.Fr.java @@ -1,7 +1,10 @@ import java.util.ArrayList; -import java.util.Iterator; +import java.util.Arrays; import java.util.LinkedList; +import java.util.Queue; import java.util.Scanner; +import javax.management.Query; + public class Fr { @@ -24,11 +27,16 @@ n = sc.nextInt(); + main = sc.nextInt(); + + nodes = null; nodes = new ArrayList<Node>(n+1); + + int[][] mat = new int[n+1][n+1]; + for (int i = 0; i < n+1; i++) { - nodes.add(null); + + nodes.add(new Node(i)); + } -// System.out.println(nodes.size()); - main = sc.nextInt(); - nodes.add(main, new Node(main, Integer.MAX_VALUE)); for (int i = 0; i < n-1; i++) { @@ -37,20 +45,70 @@ v = sc.nextInt(); - father = nodes.get(a); - if (father == null){ - tempNode = new Node(a, v); - nodes.set(a, tempNode); - - father = nodes.get(b); - father.addChild(tempNode); - }else{ - tempNode = new Node(b, v); - nodes.set(b, tempNode); - - father.addChild(tempNode); + mat[a][b] = v; + mat[b][a] = v; + } + + Queue<Integer> q = new LinkedList<Integer>(); + q.add(main); + + + int[] used = new int[n+1]; + int nodeID; + used[main] = 1; +// printMatrix(mat); + nodes.get(main).setValue(Integer.MAX_VALUE); + while(!q.isEmpty()){ + nodeID = q.poll(); + for (int i = 1; i < n+1; i++) { + if (used[i] == 0 && i != nodeID && mat[nodeID][i] != 0){ + used[i] = 1; + q.add(i); + + tempNode = nodes.get(i); + tempNode.value = mat[nodeID][i]; + nodes.get(nodeID).addChild(tempNode); +// System.out.println(nodeID+" "+i); + } } } +// System.out.println(); System.out.println(getNodeValue(nodes.get(main))); + + + + + + + +// for (int i = 0; i < n+1; i++) { +// nodes.add(new Node(i)); +// } +//// System.out.println(nodes.size()); +// +// nodes.get(main).setValue(Integer.MAX_VALUE); +//// nodes.add(main, new Node(main, Integer.MAX_VALUE)); +// +// for (int i = 0; i < n-1; i++) { +// a = sc.nextInt(); +// b = sc.nextInt(); +// v = sc.nextInt(); +// +// father = nodes.get(a); +// if (father == null){ +// tempNode = new Node(a, v); +// nodes.set(a, tempNode); +// +// father = nodes.get(b); +// father.addChild(tempNode); +// }else{ +// tempNode = new Node(b, v); +// nodes.set(b, tempNode); +// +// father.addChild(tempNode); +// } +// } +// +// System.out.println(getNodeValue(nodes.get(main))); } sc.close(); @@ -58,4 +116,10 @@ + static void printMatrix(int[][]array){ + for (int i = 0; i < array.length; i++) { + System.out.println(Arrays.toString(array[i])); + } + } + static int getNodeValue(Node node){ if (node.child.size() == 0){ @@ -82,8 +146,7 @@ Node ancestor; - public Node(int id, int value) { + public Node(int id) { super(); this.id = id; - this.value = value; child = new LinkedList<Node>(); @@ -95,3 +158,7 @@ } + void setValue(int value){ + this.value = value; + } + } \ No newline at end of file