제출 #169115

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
169115		nafis_shifat	Bosses (BOI16_bosses)	C++14	100 / 100	1216 ms	732 KiB

bosses

#include<bits/stdc++.h>
#define ll long long 
#define pii pair<int,int>
#define f first
#define s second
using namespace std;
const ll inf=2e9+10;
const int mxn=5e3+5;
vector<int> tree[mxn];
int n;
ll bfs(int root)
{
	ll dist[mxn];

	for(int i=0;i<mxn;i++)dist[i]=inf;


	queue<int> q;
	q.push(root);
	dist[root]=1;
	while(!q.empty())
	{
		int u=q.front();
		q.pop();

		for(int i:tree[u])
		{
			if(dist[i]==inf)q.push(i);
			dist[i]=min(dist[i],dist[u]+1);
		}

	}
	
	ll mx=-1;

	for(int i=1;i<=n;i++)mx=max(mx,dist[i]);
	if(mx==inf)return inf;
	ll cur=0;
	for(int i=1;i<=n;i++)cur+=dist[i];
	return cur;

	
}
int main()
{
	
	cin>>n;


	for(int i=1;i<=n;i++)
	{
		int k;
		cin>>k;
		for(int j=0;j<k;j++)
		{
			int v;
			cin>>v;
			tree[v].push_back(i);
		}
	}

	ll res=inf;





	for(int i=1;i<=n;i++)
	{    
	    res=min(res,bfs(i));
	}
	cout<<res<<endl;




	
}

• Subtask 1: 22 / 22
• Subtask 2: 45 / 45
• Subtask 3: 33 / 33