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