Untitled
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...