Submission #235312

#TimeUsernameProblemLanguageResultExecution timeMemory
235312parsa_mobedBosses (BOI16_bosses)C++14
100 / 100
730 ms888 KiB
#include <bits/stdc++.h>

using namespace std;
const int N = 5e3 + 5;
int dis[N], res, cnt, n, ans = 1e9;
vector <int> g[N];

void BFS(int v) {
    memset(dis, 31, sizeof dis), res = cnt = 0;
    queue <int> q;
    dis[v] = 0, q.push(v);
    while (!q.empty()) {
        v = q.front(), q.pop();
        res += dis[v] + 1, cnt++;
        for (int u : g[v]) if (dis[v] + 1 < dis[u]) dis[u] = dis[v] + 1, q.push(u);
    }
    if (cnt == n) ans = min(ans, res);
}

int main() {
  	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        int k; cin >> k;
        for (int j = 0; j < k; j++) {
            int u; cin >> u;
            g[u].push_back(i);
        }
    }
    for (int i = 1; i <= n; i++) BFS(i);
    cout << ans << "\n";

    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...