Submission #1182431

#TimeUsernameProblemLanguageResultExecution timeMemory
1182431boclobanchatBosses (BOI16_bosses)C++20
100 / 100
431 ms98648 KiB
#include<bits/stdc++.h>
using namespace std;
const int MAXN=5005;
vector<int> ds[MAXN];
int dp[MAXN][MAXN];
queue<int> Q;
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		int m;
		cin>>m;
		while(m--)
		{
			int res;
			cin>>res;
			ds[res].push_back(i);
		}
	}
	long long ans=1e18;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++) dp[i][j]=1e9*(i!=j);
		Q.push(i);
		while(!Q.empty())
		{
			int a=Q.front();
			Q.pop();
			for(auto v:ds[a]) if(dp[i][v]>dp[i][a]+1) dp[i][v]=dp[i][a]+1,Q.push(v);
		}
		long long res=0;
		for(int j=1;j<=n;j++) res+=dp[i][j]+1;
		ans=min(ans,res);
	}
	cout<<ans;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...