제출 #1270897

#제출 시각아이디문제언어결과실행 시간메모리
1270897cmiucBosses (BOI16_bosses)C++20
67 / 100
4 ms584 KiB
#include <iostream>
#include <queue>

using namespace std;
vector<int> nei[5005];
long long n, ans = 1e17, seen[505];

void bfs(int s, long long Ans = 0, int ver = 0){
	queue<pair<int,int>> Q;
	Q.push({s, 1});
	seen[s] = s;

	while (Q.size() > 0){
		auto [u, h] = Q.front();
		Q.pop();
		Ans += h;
		ver++;
		for (int i : nei[u]){
			if (seen[i] != s)
				seen[i] = s, Q.push({i, h + 1});
		}
	}
	if (ver == n)
		ans = min(ans, Ans);
}

int main(){
	cin>>n;

	for (int i=1, k, p;i<=n;i++){
		cin>>k;
		for (int j=1;j<=k;j++){
			cin>>p;
			nei[p].push_back(i);
		}
	}

	for (int i=1;i<=n;i++)
		bfs(i);
	cout<<ans<<'\n';
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...