Untitled

mail@pastecode.io avatar
unknown
plain_text
7 months ago
2.7 kB
0
Indexable
Never
import java.util.Scanner;

public class Solution {
	static int M, index, cnt, res;
	static int[] count, gun, visit;
	static int[][] adlist, admatrix;
	static int[] stack;


	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for (int t = 1; t <= T; t++) {
			M = sc.nextInt();

			count = new int[M];
			gun = new int[M];
			visit = new int[M];
			adlist = new int[M][M];
			admatrix = new int[M][M];
			stack = new int[M];
			index = -1;
			cnt = 0;
			res = 0;
			for (int i = 0; i < M; i++) {
				int x = sc.nextInt();
				gun[x] = sc.nextInt();
				count[x] = sc.nextInt();
				for (int j = 0; j < count[x]; j++) {
					int y = sc.nextInt();
					admatrix[x][y] = 1;
				}
				

			}
			for(int i=0;i<M;i++ ){
				for(int j=0; j<M; j++){
					if(admatrix[i][j]==1){
						adlist[i][j] = gun[i]+gun[j];
						adlist[j][i] = gun[i]+gun[j];
					}
				}
			}

			for (int i = 0; i < M; i++) {
				for (int j = 0; j <M; j++) {
					System.out.print(admatrix[i][j] + " ");
				}
				System.out.println();
			}
			for (int i = 0; i < M; i++) {
				for (int j = 0; j <M; j++) {
					System.out.print(adlist[i][j] + " ");
				}
				System.out.println();
			}

			for (int i = 0; i < M; i++) {
				if (visit[i] == 1) {
					continue;
				} else {
					dfs(i);
				}
			}
			
			System.out.println("Case #1");
			System.out.println(res);

		}
		sc.close();
	}

	private static void dfs(int i) {
		// TODO Auto-generated method stub
		if (visit[i] == 1) {
			

			int x = stack[0];
			int y = stack[1];
			res += x + y;
			return;
		}

		for (int k = 0; k < M; k++) {
			if (admatrix[i][k] == 1 && visit[k] == 0) {
				visit[i] = 1;
				index++;
				stack[index] = gun[i];
				dfs(k);
			}

		}
	}

}
------------------------------------------
main{
	ans=0;
	for(int i=0; i<N; i++){
		for(int j=0; j<N;j++){
			visit[j] = true;
		}
		check =false;
		dfs(i, i, i, 1500000, i,i);
		if(check){
			i--;
		}
	}
}


void dfs(int curV,int strV, int preV, int min, int num1,int num2){
	visit[curV] = true;
	for(int i=0; i<N; i++){
		if(i != preV && arr[curV][i]==1 && !check){
			int sumGun = gun[curV] + gun[i];
			
			if(visit[i] && i== strV){
				if(min<sumGun){
					ans += min;
					arr[num1][num2] = 0;
					arr[num2][num1] = 0;
				}else{
					ans+= sumGun;
					arr[curV][i] = 0;
					arr[i][curV] = 0;
				}
				check = true;
				return;
			}
			if(!visit[i]){
				if(min<sumGun){
					dfs(i, strV, curV, min, num1, num2);
				}else{
					dfs(i, strV, curV, sumGun, curV, i);
				}
			}
		}
	}
}