Submission #1366162

#TimeUsernameProblemLanguageResultExecution timeMemory
1366162ivazivaBosses (BOI16_bosses)C++20
100 / 100
355 ms752 KiB
#include <bits/stdc++.h>

using namespace std;

#define MAXN 5005
#define int long long 

int n;
vector<int> adj[MAXN];
int dist[MAXN];
queue<int> bfsq;
int answer=LLONG_MAX;

void bfs(int root)
{
	for (int node=1;node<=n;node++) dist[node]=INT_MAX;
	dist[root]=1;bfsq.push(root);
	while (!bfsq.empty())
	{
		int node=bfsq.front();bfsq.pop();
		for (int sled:adj[node])
		{
			if (dist[sled]!=INT_MAX) continue;
			dist[sled]=dist[node]+1;bfsq.push(sled);
		}
	}
	int solution=0;for (int node=1;node<=n;node++) solution+=dist[node];
	answer=min(answer,solution);
}

int32_t main()
{
	cin>>n;
	for (int node=1;node<=n;node++)
	{
		int number;cin>>number;
		for (int pos=1;pos<=number;pos++) {int sled;cin>>sled;adj[sled].push_back(node);}
	}
	for (int root=1;root<=n;root++) bfs(root);
	cout<<answer<<endl;
}
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...