제출 #791136

#제출 시각아이디문제언어결과실행 시간메모리
791136shoryu386Bosses (BOI16_bosses)C++17
100 / 100
520 ms596 KiB
#include <bits/stdc++.h>
using namespace std;

int main(){
	int n; cin >> n;
	vector<int> adjList[n]; //who accepts this person
	for (int x = 0; x < n; x++){
		int num, temp;
		cin >> num;
		
		for (int y = 0; y < num; y++){
			cin >> temp;
			adjList[temp-1].push_back(x);
		}
	}
	
	//try every person as root, perform bfs style
	long long bestans = LONG_LONG_MAX;
	for (int x = 0; x < n; x++){
		int depths[n]; //also functions as visited
		memset(depths, -1, sizeof(depths));
		queue<pair<int, int>> bfs; 
		depths[x] = 1; //1 for root (a bit unconventional but who cares)
		
		bfs.push(make_pair(x, 1));
		
		while (!bfs.empty()){
			int front = bfs.front().first;
			int d = bfs.front().second;
			bfs.pop();
			for (int y : adjList[front]){
				if (depths[y] == -1){
					//don't touch already used nodes
					depths[y] = d+1;
					bfs.push(make_pair(y, d+1));
				}
			}
		}
		
		bool failed = false;
		long long ans = 0;
		for (int y = 0; y < n; y++){
			if (depths[y] == -1){ failed = true; break;}
			else ans += depths[y];
		}
		
		if (!failed) bestans = min(ans, bestans);
	}
	cout << bestans;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...