제출 #537856

#제출 시각아이디문제언어결과실행 시간메모리
537856GurbanBosses (BOI16_bosses)C++17
100 / 100
629 ms664 KiB
#include "bits/stdc++.h"
using namespace std;

using ll = long long;

const int maxn=5e3+5;
int n;
int dis[maxn];
vector<int>E[maxn];

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);

	cin >> n;
	for(int i = 1;i <= n;i++){
		int sz; cin >> sz;
		for(int j = 0;j < sz;j++){
			int p; cin >> p;
			E[p].push_back(i);
		}
	}

	queue<int>q;
	int ans = 1e9;
	for(int i = 1;i <= n;i++){
		for(int j = 1;j <= n;j++) dis[j] = 1e9;
		dis[i] = 1;
		q.push(i);
		while(!q.empty()){
			int x = q.front(); q.pop();
			for(auto j : E[x]){
				if(dis[j] > dis[x] + 1){
					dis[j] = dis[x] + 1;
					q.push(j);
				}
			}
		}
		bool tr = 0;
		int nw = 0;
		for(int j = 1;j <= n;j++){
			if(dis[j] == 1e9){
				tr = 1;
				break;
			}
			nw += dis[j];
		}
		if(!tr) ans = min(ans,nw);
	}
	cout<<ans;
}
/*
4
1 4
3 1 3 4
2 1 2
1 3
*/
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...