Submission #108512

#TimeUsernameProblemLanguageResultExecution timeMemory
108512maruiiBosses (BOI16_bosses)C++14
100 / 100
821 ms836 KiB
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
#define ff first
#define ss second

vector<int> edge[5001];
bool vis[5001];

int main(){
	ios_base::sync_with_stdio(0), cin.tie(0);
	int N; cin>>N;
	for(int i=1; i<=N; ++i){
		int k; cin>>k;
		while(k--){
			int x; cin>>x;
			edge[x].push_back(i);
		}
	}
	int ans = 1e9;
	for(int i=1; i<=N; ++i){
		queue<pii> q;
		int sum = 0, cnt = 0;
		memset(vis+1, 0, N);
		q.emplace(i, 1); vis[i] = 1;
		while(q.size()){
			auto x = q.front(); q.pop();
			sum += x.ss;
			++cnt;
			for(auto i: edge[x.ff]){
				if(vis[i]) continue;
				vis[i] = 1;
				q.emplace(i, x.ss+1);
			}
		}
		if(cnt == N) ans = min(ans, sum);
	}
	cout<<ans;
	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...