Submission #207820

#	Time	Username	Problem	Language	Result	Execution time	Memory
207820		bensonlzl	Bosses (BOI16_bosses)	C++14	100 / 100	758 ms	888 KiB

bosses

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

ll N, K, X, dist[5005];
vector<ll> employ[5005];

ll bfs(int x){
	ll sum = 0;
	for (int i = 1; i <= N; ++i) dist[i] = 1e9;
	dist[x] = 0;
	queue<int> q;
	q.push(x);
	while (!q.empty()){
		int v = q.front();
		q.pop();
		for (auto it : employ[v]){
			if (dist[it] > dist[v] + 1){
				dist[it] = dist[v] + 1;
				q.push(it);
			}
		}
	}
	for (int i = 1; i <= N; ++i){
		sum += dist[i];
	}
	return sum + N;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin >> N;
	for (int i = 1; i <= N; ++i){
		cin >> K;
		for (int j = 1; j <= K; ++j){
			cin >> X;
			employ[X].push_back(i);
		}
	}
	ll mini = 1e9;
	for (int i = 1; i <= N; ++i){
		mini = min(mini,bfs(i));
	}
	cout << mini << '\n';
}

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