제출 #1270898

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1270898		cmiuc	Bosses (BOI16_bosses)	C++20	100 / 100	386 ms	736 KiB

bosses

#include <iostream>
#include <queue>

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

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';
}

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