Submission #1092511

#TimeUsernameProblemLanguageResultExecution timeMemory
1092511___Bosses (BOI16_bosses)C++17
67 / 100
3 ms604 KiB
#include <bits/stdc++.h>
#define int long long int
#define ff first
#define ss second
#define FT ios_base::sync_with_stdio(false);cin.tie(0);
using namespace std;
int n;
const int maxn = 2e3 + 10;
const int inf = 1e15;
vector <int> adj[maxn];
bool mark[maxn];
int h[maxn];
queue <int> q;
int bfs (int r)
{
	for (int i = 1 ; i <= n ; i++)
	{
		h[i] = inf;
	}
	h[r] = 1;
	q.push(r);
	mark[r] = true;
	while (!q.empty())
	{
		int v = q.front();
		q.pop();
		for (auto u : adj[v])
		{
			if (!mark[u])
			{
				h[u] = h[v] + 1;
				q.push(u);
				mark[u] = true;
			}
		}
	}
	int sum = 0;
	for (int i = 1 ; i <= n ; i++)
	{
		sum += h[i];
		mark[i] = false;
	}
	return sum;
}
signed main() 
{
	FT;
	cin >> n;
	for (int i = 1 ; i <= n ; i++)
	{
		int k;
		cin >> k;
		while (k--)
		{
			int b;
			cin >> b;
			adj[b].push_back(i);
		}
	}
	int ans = 1e15;
	for (int i = 1 ; i <= n ; i++)
	{
		ans = min (ans , bfs(i));
	}
	cout << ans << endl;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...