Submission #1239326

#TimeUsernameProblemLanguageResultExecution timeMemory
1239326kaiboyBosses (BOI16_bosses)C++20
100 / 100
318 ms752 KiB
#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

const int   N = 5000;
const int INF = 0x3f3f3f3f;

vector<int> ej[N];
int dd[N], qu[N];

int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL);
	int n; cin >> n;
	for (int i = 0; i < n; i++) {
		int k; cin >> k;
		while (k--) {
			int p; cin >> p, p--;
			ej[p].push_back(i);
		}
	}
	int ans = INF;
	for (int r = 0; r < n; r++) {
		for (int i = 0; i < n; i++)
			dd[i] = n;
		int s = 0, cnt = 0; dd[qu[cnt++] = r] = 0;
		for (int h = 0; h < cnt; h++) {
			int i = qu[h], d = dd[i] + 1; s += d;
			for (int j : ej[i])
				if (dd[j] == n)
					dd[qu[cnt++] = j] = d;
		}
		if (cnt == n)
			ans = min(ans, s);
	}
	cout << ans << '\n';
	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...