Untitled

package tctt;

import java.io.FileInputStream;
import java.util.Scanner;

public class Solution {
	static int[][] a;
	static int[] chuaxet;
	static boolean cycle;
	static int n, k;
	static int[] b;
	static int[] c;
	static int min, td1, td2;
	static int td;
	
	public static void main(String args[]) throws Exception{
		System.setIn(new FileInputStream("src/tctt/input.txt"));
		Scanner sc = new Scanner(System.in);
		int T;
		int Answer;
		T=sc.nextInt();
		for(int test_case = 1; test_case <= T; test_case++){
			n = sc.nextInt();
			b = new int[n];
			a = new int[n][n];
			
			for(int i = 0; i < n; i++){
				int x = sc.nextInt();
				b[i] = sc.nextInt();
				int z = sc.nextInt();
				for(int j = 0; j < z; j++){
					int y = sc.nextInt();
					a[x][y] = 1;
				}
			}
			
			/*for(int i = 0; i < n; i++){
				for(int j = 0; j < n; j++){
					System.out.print(a[i][j] + " ");
				}
				System.out.println();
			}
*/
            chuaxet = new int[n];
			
			for(int i = 0; i < n; i++){
				chuaxet[i] = 0;
			}
				
			int kq = 0;
			
			for(int i = 0; i < n; i++){
				td = -1;
				cycle = false;
				c = new int[n];
				k = 0;
				for(int j = 0; j < n; j++){
					chuaxet[j] = 0;
				}
				dfs(i,i);

				while(cycle){
					int res = td;
					int temp = -1;
					
					
					int[] h = new int[k];
					int l = 0;
					
					for(int u = 0; u < k; u++){
						if(chuaxet[c[u]] == 1){
							h[l] = c[u];
							l++;
						}
					}
					
					for(int u = 0; u < l; u++){
						if(h[u] == res){
							temp = u;
							break;
						}
					}
					
					min = b[h[temp]] + b[h[l-1]];
					int x1 = h[temp], x2 = h[l-1];;
					for(int u = temp; u < l - 1; u++){
						if(min > b[h[u]] + b[h[u+1]]){
							min = b[h[u]] + b[h[u+1]];
							x1 = h[u];
							x2 = h[u+1];
						}
					}
					
					kq += min;
					a[x1][x2] = 0;
					a[x2][x1] = 0;
					
					td = -1;
					cycle = false;
					c = new int[n];
					k = 0;
					for(int j = 0; j < n; j++){
						chuaxet[j] = 0;
					}
					
					dfs(i,i);
				}	
		    }

			System.out.println("Case #" + test_case);
			System.out.println(kq);
		}
	}
	
	public static void dfs(int pre, int v){
		c[k] = v;
		k++;
		chuaxet[v] = 1;
		for(int i = 0; i < n; i++){
			if(a[v][i] != 0 && chuaxet[i] == 0){
				dfs(v, i);
			}else if(chuaxet[i] == 1 && a[v][i] != 0 && pre!= i){
				td = i;
				cycle = true;
				//return;
			}
			if(cycle){
				return;
			}
		}
		chuaxet[v] = 2;
	}
}





















package tctt;

import java.io.FileInputStream;
import java.util.Scanner;

public class SolutionDj {
	static int[][] a;
	static int[] chuaxet;
	static boolean cycle;
	static int n, k, sum;
	static int[] b;
	static int[] c;
	static int[][] x;
	
	public static void main(String args[]) throws Exception{
		System.setIn(new FileInputStream("src/tctt/input.txt"));
		Scanner sc = new Scanner(System.in);
		int T;
		int Answer;
		T=sc.nextInt();
		for(int test_case = 1; test_case <= T; test_case++){
			n = sc.nextInt();
			b = new int[n];
			a = new int[n][n];
			
			for(int i = 0; i < n; i++){
				int x = sc.nextInt();
				b[i] = sc.nextInt();
				int z = sc.nextInt();
				for(int j = 0; j < z; j++){
					int y = sc.nextInt();
					a[x][y] = 1;
				}
			}
			
			/*for(int i = 0; i < n; i++){
				for(int j = 0; j < n; j++){
					System.out.print(a[i][j] + " ");
				}
				System.out.println();
			}*/
			
			x = new int[n][n];

            for(int i = 0; i < n; i++){
            	for(int j = 0; j < n; j++){
            		if(a[i][j] == 1){
            			x[i][j] = b[i] + b[j];
            		}
            	}
            }
            
           /* System.out.println();
            for(int i = 0; i < n; i++){
            	for(int j = 0; j < n; j++){
            		System.out.print(x[i][j] + " ");
            	}
            	System.out.println();
            }
			*/
            
            sum = 0;
            for(int i = 0; i < n-1; i++){
            	for(int j = i+1; j < n; j++){
            		sum += x[i][j];
            	}
            }
            
            //System.out.println("sum " + sum);

            prim();
            
			//System.out.println("Case #" + test_case);
			//System.out.println(kq);
		}
	}
	
	 public static void prim(){
		 int parent[] = new int[n];
	     int key[] = new int[n];
	     boolean visit[] = new boolean[n];
	        
	     for (int i = 0; i < n; i++) {
	         key[i] = -1;
	         visit[i] = false;
	         parent[i] = -1;
	     }
	 
	     key[0] = 0;
	 
	 
	     for (int i = 0; i < n - 1; i++) {
	          int max = -1, td = -1;
	        	 
	          for (int j = 0; j < n; j++){
	               if (visit[j] == false && key[j] > max) {
	               max = key[j];
	               td = j;
	          }
	     }
	                
	             
	     int u = td;
	     visit[u] = true;

	     for (int k = 0; k < n; k++){
	         if (visit[k] == false){
	                 if(x[u][k] > key[k]){
	                    parent[k] = u;
	                    key[k] = x[u][k];
	                 }
	             }
	         }    
	     }
	        
	     int tong = 0;
	     for(int i = 1; i < n; i++){
//	        System.out.println(parent[i] + " - " + i + " " + key[i]);
	        tong += key[i];
	     }
	     System.out.println(sum-tong);
	 }
}