Submission #1040416

#TimeUsernameProblemLanguageResultExecution timeMemory
1040416vjudge1Bosses (BOI16_bosses)C++17
100 / 100
434 ms772 KiB
// 23 - 12 - 23 

#include<bits/stdc++.h>

using namespace std;

#define read() ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define day() time_t now = time(0);char* x = ctime(&now);cerr<<"Right Now Is : "<<x<<"\n"

#define ii pair<int,int>
#define X first
#define Y second 

const long long MAX = (int)5000 + 5;
const long long INF = (int)1e9;
const long long MOD = (int)1e9 + 7;

int n;
vector<int> adj[MAX];

signed main(){
	
	read();
	
	cin >> n;
	
	for(int i = 1,k;i <= n;i++){
		cin >> k;
		for(int j = 1,x;j <= k;j++){
			cin >> x;
			adj[x].push_back(i);
		}
	}
	
	int res = INF;
	
	for(int i = 1;i <= n;i++){
		vector<int> visited(n + 5,-1);
		visited[i] = 1;
		deque<int> h;
		h.push_back(i);
		int sum = 1;
		//cout << i << " :\n";
		while(!h.empty()){
			int u = h.front();
			h.pop_front();
			//cout << u << " " << visited[u] << "\n";
			for(auto v : adj[u]){
				if(visited[v] == -1){
					visited[v] = visited[u] + 1;
					sum += visited[v];
					h.push_back(v);
				}
			}
		}
		for(int j = 1;j <= n;j++){
			if(visited[j] == -1)sum = INF;
		}
		res = min(res,sum);
	}
	cout << res;
	
	
}









#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...