Untitled

mail@pastecode.io avatar
unknown
plain_text
a month ago
1.5 kB
0
Indexable
Never
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>

using namespace std;

int N;
int arr[101][101];
int cannon[101];

int visit[101], check;

int ans, sumCannon;

void DFS(int start, int pre, int cur, int min, int point1, int point2) {
	visit[cur] = 1;
	for (int i = 0; i < N; i++) {
		if (i != pre && arr[cur][i] == 1 && check == false) {
			sumCannon = cannon[cur] + cannon[i];
			
			if (visit[i] == 1 && i == start) {
				if (min < sumCannon) {
					ans += min;
					arr[point1][point2] = arr[point2][point1] = 0;
				}
				else {
					ans += sumCannon;
					arr[cur][i] = arr[i][cur] = 0;
				}
				check = 1;
				return;
			}

			if (visit[i] == 0) {
				if (min < sumCannon) {
					DFS(start, cur, i, min, point1, point2);
				}
				else {
					DFS(start, cur, i, sumCannon, cur, i);
				}
			}
		}
	}
}

int main() {
	int T;
	freopen("input.txt", "r", stdin);
	cin >> T;

	for (int tc = 1; tc <= T; tc++) {
		cin >> N;
		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++) {
			cin >> v;
			cin >> cannon[v] >> cnt;
			for (int j = 0; j < cnt; j++) {
				cin >> w;
				arr[v][w] = 1;
			}
		}

		ans = 0;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				visit[j] = 0;
			}
			check = 0;
			DFS(i, i, i, 1500000, i, i);
			if (check) i--;
		}
		cout << "Case #" << tc << endl << ans << endl;
	}
	return 0;
}