제출 #258664

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

const int N = 5e3+5, INF = 1e9;
int n;
vector<int> adj[N];

void read() {
	cin >> n;
	for(int i = 1; i <= n; i++) {
		int c; cin >> c;
		for(int j = 0; j < c; j++) {
			int v; cin >> v;
			adj[v].push_back(i);
		}
	}
}

int bfs(int st) {
	int cur = 0;
	bool vis[n+1] = {0};
	queue<pair<int, int>> q;
	q.push({st, 1});

	// cerr << "---" << st << '\n';
	while(!q.empty()) {
		int u = q.front().first, h = q.front().second; q.pop();
		if(!vis[u]) {
			// cerr << u << ' ' << h << '\n';
			vis[u] = 1;
			cur += h;
			for(int v : adj[u]) if(!vis[v]) {
				q.push({v, h+1});
			}
		}
	}

	for(int i = 1; i <= n; i++) if(!vis[i]) {
		return INF;
	}
	return cur;
}

void solve() {
	int ans = INF;
	for(int i = 1; i <= n; i++) {
		ans = min(ans, bfs(i));
	}
	cout << ans << '\n';
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	read();
	solve();
	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...