제출 #1349984

#제출 시각아이디문제언어결과실행 시간메모리
1349984kantaponzBosses (BOI16_bosses)C++20
100 / 100
361 ms748 KiB
#include <bits/stdc++.h>
using namespace std;

#define ll long long

const int nx = 5005;

int n;
ll ans = 1e18;
vector<int> adj[nx];

int main() {
    ios_base::sync_with_stdio(0), cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        int k; cin >> k;
        while (k--) {
            int u; cin >> u;
            adj[u].emplace_back(i);
        }
    }

    for (int i = 1; i <= n; i++) {
        ll dist[n + 1];
        fill(dist, dist + n + 1, 1e9);
        queue<pair<int,int>> q;
        ll tmp = 0;
        dist[i] = 1;
        q.emplace(1, i);
        while (!q.empty()) {
            auto [w, u] = q.front();
            q.pop();
            if (dist[u] < w) continue;
            for (auto v : adj[u]) {
                if (dist[v] <= w + 1) continue;
                dist[v] = w + 1;
                q.emplace(dist[v], v);
            }
        }
        bool chk = 1;
        for (int i = 1; i <= n; i++) {
            if (dist[i] == 1e9) chk = 0;
        }
        if (!chk) continue;
        for (int i = 1; i <= n; i++) tmp += dist[i];
        ans = min(ans, tmp);
    }
    cout << ans;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...