Untitled

mail@pastecode.io avatarunknown
plain_text
a month ago
2.5 kB
1
Indexable
Never
package tan_cong_thanh_tri;

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

public class Solution {
	static boolean w;
	static int n, result;
	static int[][] a;
	static int[] visit=new int[101];
	static int[] may=new int[101];
	
	
	public static void duyet(int dau, int cuoi, int truoc, int minx, int miny, int min){
		visit[cuoi] = 1;
		for(int i = 0; i < n; i++){
			if(visit[i] == 0 && w == false){
				if(may[cuoi] + may[i] < min){
					duyet(dau, i, cuoi, cuoi, i, may[cuoi] + may[i]);
				}else{
					duyet(dau, i, cuoi, minx, miny, min);
				}
			}
			if(i == dau && i != truoc && visit[i] == 1){
				if(may[cuoi]+may[i]<min){
					minx = cuoi;
					miny = i;
					min = may[cuoi] +may[i];
					
				}
				result += min;
				a[minx][miny] = 0;
				a[miny][minx] = 0;
				w = true;
				return;
			}
		}
	}
	
	
	
	
	public static void DFS(int dau, int cuoi, int truoc, int minx, int miny, int min){
		visit[cuoi] = 1;
//		System.out.println(y);
		for(int i = 0; i < n; i++){
			if(a[cuoi][i] == 1 && w==false){
				if(visit[i] == 0 && i != truoc){
					if(may[cuoi]+may[i]<min){
						DFS(dau,i,cuoi,cuoi,i,may[cuoi]+may[i]);
					}else{
						DFS(dau,i,cuoi,minx,miny,min);
					}
				}
				if(i == dau && i!=truoc && visit[i]==1){
					if(may[cuoi]+may[i]<min){
						minx=cuoi;
						miny=i;
						min=may[cuoi]+may[i];
					}
					result+=min;
					a[minx][miny]=0;
					a[miny][minx]=0;
					w=true;
					return;
				}
			}
		}
	}
	

	public static void main(String[] args) {
		try {
			System.setIn(new FileInputStream("input.txt"));
		} catch (FileNotFoundException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
		Scanner scanner = new Scanner(System.in);
		int test = scanner.nextInt();
		for (int t = 1; t <= test; t++) {
			// input
			n = scanner.nextInt();
			a = new int[n][n];
			for (int i = 0; i < n; i++) {
				int m = scanner.nextInt();
				may[m] = scanner.nextInt();
				int k = scanner.nextInt();
				for (int j = 0; j < k; j++) {
					int x = scanner.nextInt();
					a[m][x] = 1;
					a[x][m] = 1;
				}
			}		
			
			result = 0;
			for(int i=0;i<n;i++){
				for(int j=0;j<n;j++) visit[j]=0;
				w=false;
				visit[i]=1;
				DFS(i,i,i,i,i,15000);
				if(w==true)
					i--;
			}

			System.out.println("Case #" + t + "\n" + result);
		}
		scanner.close();
	}
}