Submission #1200537

#TimeUsernameProblemLanguageResultExecution timeMemory
1200537PlayVoltzBosses (BOI16_bosses)C++20
100 / 100
536 ms728 KiB
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define pii pair<int, int>
#define mp make_pair
#define pb push_back

int n;
vector<vector<int> > graph;

int bfs(int start){
	int sum=0;
	bitset<5005> visited;
	queue<pii> q;
	q.push(mp(start, 1));
	while (!q.empty()){
		int cnode=q.front().first, dep=q.front().second;
		q.pop();
		if (visited[cnode])continue;
		visited[cnode]=1;
		sum+=dep;
		for (auto num:graph[cnode]){
			if (!visited[num])q.push(mp(num, dep+1));
		}
	}
	return (visited.count()==n ? sum:LLONG_MAX);
}

int32_t main(){
	int m, a;
	cin>>n;
	graph.resize(n);
	for (int i=0; i<n; ++i){
		cin>>m;
		while (m--){
			cin>>a;--a;
			graph[a].pb(i);
		}
	}
	int minnum=LLONG_MAX;
	for (int i=0; i<n; ++i)minnum=min(minnum, bfs(i));
	cout<<minnum;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...