제출 #223569

#제출 시각아이디문제언어결과실행 시간메모리
223569kshitij_sodaniBosses (BOI16_bosses)C++17
100 / 100
790 ms760 KiB
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
#define a first
#define b second
#define pb push_back
vector<int> adj[5001];
int n;
int bfs(int no){
	int dist[n];
	for(int i=0;i<n;i++){
		dist[i]=-1;
	}
	dist[no]=0;
	queue<int> dd;
	dd.push(no);
	while(dd.size()){
		int x=dd.front();
		dd.pop();
		for(auto jj:adj[x]){
			if(dist[jj]==-1 or dist[jj]>dist[x]+1){
				dist[jj]=dist[x]+1;
				dd.push(jj);
			}
		}
	}

	for(int i=0;i<n;i++){
		if(dist[i]==-1){
			return -1;
		}
	}
	int ans=n;
	for(int i=0;i<n;i++){
		ans+=dist[i];
	}


	return ans;
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin>>n;

	for(int i=0;i<n;i++){
		int k;
		cin>>k;
		int aa;
		for(int j=0;j<k;j++){
			cin>>aa;
			adj[aa-1].pb(i);
		}
	}
	int mi=1000000000;
	for(int i=0;i<n;i++){
		int ma=bfs(i);
		if(ma>-1){
			mi=min(mi,ma);
		}
	}
	cout<<mi<<endl;
	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...