Untitled

mail@pastecode.io avatar
unknown
plain_text
7 months ago
1.9 kB
2
Indexable
Never
package Graph;

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

class KhongMinh {

	public static int V;
	public static int[][] adj;
	public static int[] count;
	public static int min;
	static boolean[] visited;
	static boolean check = false;
	static int total = 0;

	static void DFS(int curv, int strv, int pre, int min, int num1, int num2) {
		visited[curv] = true;
		for (int i = 0; i < V; i++) {
			if (i != pre && adj[curv][i] == 1 && !check) {
				int sumGun = count[curv] + count[i];
				if (visited[i] && i == strv) {
					if (min < sumGun) {
						total += min;
						adj[num2][num1] = 0;
						adj[num1][num2] = 0;
					} else {
						total += sumGun;
						adj[curv][i] = 0;
						adj[i][curv] = 0;
					}
					check = true;
					return;
				}
				if (!visited[i]) {
					if (min < sumGun) {
						DFS(i, strv, curv, min, num1, num2);
					} else {
						DFS(i, strv, curv, sumGun, curv, i);
					}
				}
			}
		}
	}

	public static void main(String[] args) throws FileNotFoundException {
		System.setIn(new FileInputStream("Text"));
		Scanner scanner = new Scanner(System.in);
		int tc = scanner.nextInt();
		for (int Case = 1; Case <= tc; Case++) {
			total = 0;
			V = scanner.nextInt();
			adj = new int[V][V];
			count = new int[V];
			visited = new boolean[V];
			for (int i = 0; i < V; i++) {
				int index = scanner.nextInt();
				count[index] = scanner.nextInt();
				int gr = scanner.nextInt();
				for (int j = 0; j < gr; j++) {
					int x = scanner.nextInt();
					adj[i][x] = 1;
				}
			}

			for (int i = 0; i < V; i++) {
				for (int j = 0; j < V; j++) {
					visited[j]=false;
				}
				check = false;
				min = Integer.MAX_VALUE;
				DFS(i, i, i, min, i, i);
				if(check){
					i--;
				}
			}
			System.out.println(total);
		}
	}
}