Untitled

 avatar
unknown
plain_text
2 years ago
1.7 kB
5
Indexable
import java.util.Scanner;

public class Solution {
	static int N;
	static int[][] arr = new int[101][101];
	static int[] gun = new int[101];
	static boolean[] visit = new boolean[101];
	static int ans;
	static boolean check;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();

		for (int tc = 1; tc <= T; tc++) {
			N = sc.nextInt();

			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					arr[i][j] = 0;
				}
			}

			int v, w, cnt;
			for (int i = 0; i < N; i++) {
				v = sc.nextInt();
				gun[v] = sc.nextInt();
				cnt = sc.nextInt();
				for (int j = 0; j < cnt; j++) {
					w = sc.nextInt();
					arr[v][w] = 1;
				}
			}

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

			System.out.println("Case #" + tc);
			System.out.println(ans);
		}
		sc.close();
	}

	static 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[num2][num1] = 0;
						arr[num1][num2] = 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);
					}
				}
			}
		}
	}
}
Editor is loading...