Submission #1358423

#TimeUsernameProblemLanguageResultExecution timeMemory
1358423pinbuBosses (BOI16_bosses)C++20
100 / 100
340 ms732 KiB
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

const int N = 5005;

int n;
vector<int> adj[N];
int d[N];

signed main(void) {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    
    cin >> n;
    for (int i = 1, j; i <= n; i++) {
    	cin >> j;
    	while (j--) {
    		int v; cin >> v;
    		adj[v].emplace_back(i);
    	}
    }
    int ans = 2e9 + 7;
    for (int i = 1; i <= n; i++) {
    	for (int j = 1; j <= n; j++) d[j] = -1;
    	d[i] = 0;
    	queue<int> q;
    	q.push(i);
    	while (q.size()) {
    		int u = q.front();
    		q.pop();
    		for (int v: adj[u]) if (d[v] < 0) {
    			d[v] = d[u] + 1;
    			q.push(v);
    		}
    	}
    	int res = 0;
    	for (int j = 1; j <= n; j++) {
    		if (d[j] < 0) {
    			res = 2e9 + 7;
    			break;
    		}
    		res += d[j];
    	}
    	ans = min(ans, res + n);
    }
    cout << ans;
    
    return 0;
}
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...