제출 #218600

#제출 시각아이디문제언어결과실행 시간메모리
218600KCSCBosses (BOI16_bosses)C++14
100 / 100
797 ms760 KiB
#include <bits/stdc++.h>
using namespace std;

const int DIM = 5005;

vector<int> edg[DIM];
int mrk[DIM];

int main(void) {
#ifdef HOME
	freopen("bosses.in", "r", stdin);
	freopen("bosses.out", "w", stdout);
#endif
	int n; cin >> n;
	for (int i = 1; i <= n; ++i) {
		int k; cin >> k;
		for (int j = 1; j <= k; ++j) {
			int x; cin >> x;
			edg[x].push_back(i);
		}
	}
	int ans = (1 << 30);
	for (int s = 1; s <= n; ++s) {
		for (int i = 1; i <= n; ++i)
			mrk[i] = 0;
		mrk[s] = 1;
		deque<int> que(1, s);
		int cst = 0;
		for (; que.size(); que.pop_front()) {
			int x = que.front();
			cst += mrk[x];
			for (int y : edg[x]) if (!mrk[y]) {
				mrk[y] = mrk[x] + 1;
				que.push_back(y);
			}
		}
		for (int i = 1; i <= n; ++i)
			if (!mrk[i])
				cst = (1 << 30);
		ans = min(ans, cst);
	}
	cout << ans << endl;
	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...