Source code for submission s876

Go to diff to previous submission

Fr.java

  1. import java.util.ArrayList;
  2. import java.util.Arrays;
  3. import java.util.LinkedList;
  4. import java.util.Queue;
  5. import java.util.Scanner;
  6.  
  7. import javax.management.Query;
  8.  
  9.  
  10. public class Fr {
  11.  
  12. 	public static void main(String[] args) {
  13. 		Scanner sc = new Scanner(System.in);
  14.  
  15. 		int n;
  16. 		int main;
  17. 		ArrayList<Node> nodes;
  18.  
  19. 		int a;
  20. 		int b;
  21. 		int v;
  22. 		Node tempNode;
  23. 		Node father;
  24. 		while(sc.hasNextInt()){	
  25. 			a = 0;
  26. 			b = 0;
  27.  
  28. 			n = sc.nextInt();
  29. 			main = sc.nextInt();
  30.  
  31. 			nodes = null;
  32. 			nodes = new ArrayList<Node>(n+1);
  33.  
  34. 			int[][] mat = new int[n+1][n+1];		
  35.  
  36. 			for (int i = 0; i < n+1; i++) {
  37.  
  38. 				nodes.add(new Node(i));
  39.  
  40. 			}
  41.  
  42. 			for (int i = 0; i < n-1; i++) {
  43. 				a = sc.nextInt();
  44. 				b = sc.nextInt();
  45. 				v = sc.nextInt();
  46.  
  47. 				mat[a][b] = v; 
  48. 				mat[b][a] = v;
  49. 			}
  50.  
  51. 			Queue<Integer> q = new LinkedList<Integer>();
  52. 			q.add(main);
  53.  
  54.  
  55. 			int[] used = new int[n+1]; 
  56. 			int nodeID;
  57. 			used[main] = 1;
  58. //			printMatrix(mat);
  59. 			nodes.get(main).setValue(Integer.MAX_VALUE);
  60. 			while(!q.isEmpty()){
  61. 				nodeID = q.poll();
  62. 				for (int i = 1; i < n+1; i++) {
  63. 					if (used[i] == 0 && i != nodeID && mat[nodeID][i] != 0){
  64. 						used[i] = 1;
  65. 						q.add(i);
  66.  
  67. 						tempNode = nodes.get(i);
  68. 						tempNode.value = mat[nodeID][i];
  69. 						nodes.get(nodeID).addChild(tempNode);
  70. //						System.out.println(nodeID+" "+i);
  71. 					}
  72. 				}
  73. 			}
  74. //			System.out.println();
  75.  
  76. 			System.out.println(getNodeValue(nodes.get(main)));
  77.  
  78.  
  79.  
  80.  
  81.  
  82.  
  83.  
  84. //			for (int i = 0; i < n+1; i++) {
  85. //				nodes.add(new Node(i));
  86. //			}
  87. ////			System.out.println(nodes.size());
  88. //			
  89. //			nodes.get(main).setValue(Integer.MAX_VALUE);
  90. ////			nodes.add(main, new Node(main, Integer.MAX_VALUE));
  91. //			
  92. //			for (int i = 0; i < n-1; i++) {
  93. //				a = sc.nextInt();
  94. //				b = sc.nextInt();
  95. //				v = sc.nextInt();
  96. //				
  97. //				father = nodes.get(a);
  98. //				if (father == null){
  99. //					tempNode = new Node(a, v);
  100. //					nodes.set(a, tempNode);
  101. //					
  102. //					father = nodes.get(b);
  103. //					father.addChild(tempNode);
  104. //				}else{
  105. //					tempNode = new Node(b, v);
  106. //					nodes.set(b, tempNode);
  107. //					
  108. //					father.addChild(tempNode);
  109. //				}
  110. //			}
  111. //			
  112. //			System.out.println(getNodeValue(nodes.get(main)));
  113. 		}
  114. 		sc.close();
  115. 	}
  116.  
  117.  
  118. 	static void printMatrix(int[][]array){
  119. 		for (int i = 0; i < array.length; i++) {
  120. 			System.out.println(Arrays.toString(array[i]));
  121. 		}
  122. 	}
  123.  
  124. 	static int getNodeValue(Node node){
  125. 		if (node.child.size() == 0){
  126. 			return node.value;
  127. 		}
  128.  
  129. 		int sumV = 0;
  130. 		for (Node n : node.child) {
  131. 			sumV += getNodeValue(n);
  132. 		}
  133.  
  134. 		if (node.value > sumV){
  135. 			node.value = sumV;
  136. 			return node.value;
  137. 		}
  138. 		return node.value;
  139. 	}
  140. }
  141.  
  142. class Node{
  143. 	int id;
  144. 	int value;
  145. 	LinkedList<Node> child;
  146. 	Node ancestor;
  147.  
  148. 	public Node(int id) {
  149. 		super();
  150. 		this.id = id;
  151.  
  152. 		child = new LinkedList<Node>();
  153. //		this.ancestor = ancestor;
  154. 	}
  155.  
  156. 	void addChild(Node node){
  157. 		this.child.add(node);
  158. 	}
  159.  
  160. 	void setValue(int value){
  161. 		this.value = value;
  162. 	}
  163.  
  164. }

Diff to submission s770

Fr.java

--- 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