Submission #1159505

#TimeUsernameProblemLanguageResultExecution timeMemory
1159505nrg_studioBosses (BOI16_bosses)C++20
100 / 100
383 ms740 KiB
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pb push_back
#define pii pair<int,int>
#define f first
#define s second
#define chmin(a, b) a = min(a,b)
#define chmax(a, b) a = max(a,b)
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define F0R(i, a) for (int i = 0; i < (a); i++)
#define all(x) x.begin(),x.end()
#define v vector

const int MAX_N = 5000;
v<int> adj[MAX_N];
int dist[MAX_N];
int ans = INT_MAX;

int main() {
    ios::sync_with_stdio(false); cin.tie(0);

    int n; cin >> n;
    F0R(i,n) {
        int m; cin >> m;
        F0R(j,m) {
            int a; cin >> a;
            adj[--a].pb(i);
        }
    }
    F0R(rt,n) {
        F0R(i,n) {dist[i] = INT_MAX;}
        queue<int> q;
        q.push(rt); dist[rt] = 1;
        while (q.size()) {
            int cur = q.front(); q.pop();
            for (int x : adj[cur]) {
                if (dist[x]==INT_MAX) {
                    dist[x] = dist[cur]+1;
                    q.push(x);
                }
            }
        }
        int cand = 0;
        F0R(i,n) {
            if (dist[i]==INT_MAX) {cand = INT_MAX;}
            else if (cand!=INT_MAX) {cand += dist[i];}
        } chmin(ans,cand);
    } cout << ans << '\n';
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...