제출 #654301

#제출 시각아이디문제언어결과실행 시간메모리
654301bogdanvladmihaiBosses (BOI16_bosses)C++14
100 / 100
753 ms98704 KiB
#include <bits/stdc++.h>
using namespace std;

int main() {
	int n; cin >> n;
	vector<vector<int>> g(n);
	for (int i = 0; i < n; i++) {
		int cnt; cin >> cnt;
		for (int j = 0; j < cnt; j++) {
			int x; cin >> x;
			x--;
			g[x].push_back(i);
		}
	}
	int answer = INT_MAX;
	vector<vector<int>> dist(n, vector<int>(n, INT_MAX));
	for (int u = 0; u < n; u++) {
		queue<int> q;
		q.push(u);
		dist[u][u] = 1;
		int sum = 0, cnt = 0;
		while ((int)q.size() > 0) {
			int x = q.front();
			sum += dist[u][x];
			cnt++;
			q.pop();
			for (const int &v : g[x]) {
				if (dist[u][v] != INT_MAX) {
					continue;
				}
				dist[u][v] = dist[u][x] + 1;
				q.push(v);
			}
		}
		if (cnt == n) {
			answer = min(answer, sum);
		}
	}
	cout << answer << "\n";
	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...