Submission #533185

#TimeUsernameProblemLanguageResultExecution timeMemory
533185gilbirbBosses (BOI16_bosses)C++14
100 / 100
622 ms648 KiB
#include <bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
typedef long long ll;
using namespace std;

ll n, ans = 1e9;
vector<ll>adj[5005];
ll p[5005];

void bfs(ll s){
	memset(p, 0, sizeof(p));
	p[s] = 1;
	queue<ll>q;
	q.push(s);
	while(!q.empty()){
		ll cur = q.front();
		q.pop();
		for(int x : adj[cur]){
			if(!p[x]){
				p[x] = p[cur]+1;
				q.push(x);
			}
		}
	}
	ll total = 0;
	for(int i = 1; i <= n; i++){
		if(!p[i]) return;
		total += p[i];
	}
	ans = min(ans, total);
	return;
}

int main(){
	cin >> n;
	for(int i = 1; i <= n; i++){
		int m;
		cin >> m;
		for(int j = 1; j <= m; j++){
			ll x; cin >> x;
			adj[x].pb(i);
		}
	}
	for(int i = 1; i <= n; i++){
		bfs(i);
	}
	cout << ans << endl;
	
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...