제출 #79514

#제출 시각아이디문제언어결과실행 시간메모리
79514atoizBosses (BOI16_bosses)C++14
100 / 100
680 ms1176 KiB
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

const int MAX = 5007;
const int INF = 1e8;
int n;
vector<int> gr[MAX];

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n;
    for (int v = 1; v <= n; ++v) {
        int k, u; cin >> k;
        for (int j = 0; j < k; ++j) {
            cin >> u; gr[u].push_back(v);
        }
    }

    int ans = INF;
    for (int root = 1; root <= n; ++root) {
        vector<int> hei(n + 1, INF);
        hei[root] = 0;
		queue<int> qu;
		qu.push(root);
        while (!qu.empty()) {
			int u = qu.front(); qu.pop();
            for (int v : gr[u]) {
                if (hei[v] < INF) continue;
                hei[v] = hei[u] + 1;
                qu.push(v);
            }
        }

        int curAns = n;
        bool full = 1;
        for (int u = 1; u <= n && full; ++u) {
            if (hei[u] == INF) full = 0;
			else curAns += hei[u];
        }
        if (full) ans = min(ans, curAns);
    }
    cout << ans;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...