Untitled

mail@pastecode.io avatar
unknown
plain_text
7 months ago
1.4 kB
2
Indexable
Never
#include <iostream>

using namespace std;

int N;
int arr[101][101];
int gun[101];

int visit[101], check;

int ans;

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);
				}
			}
		}
	}
}

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 >> gun[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] = false;
			}
			check = false;
			DFS(i, i, i, 1500000, i, i);
			if (check) {
				i--;
			}
		}

		cout << "Case #" << tc << endl << ans << endl;
	}
	return 0;
}