제출 #1218923

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

typedef long long ll;

const ll inf = 1e16 + 66;

int32_t main () {

    ios_base::sync_with_stdio(0); 
    cin.tie(0); 
    cout.tie(0); 

    int N;
    cin >> N;
    vector<int> g[N];
    for (int i = 0;i < N;i ++) {
        int k;
        cin >> k;
        for (int j = 0;j < k;j ++) {
            int x;
            cin >> x;
            -- x;
            g[x].push_back(i);
        }
    }
    ll res = inf;
    for (int i = 0;i < N;i ++) {
        vector<ll> dist(N, inf);
        dist[i] = 1;
        queue<int> q;
        q.push(i); 
        while (q.size() > 0) {
            auto u = q.front();
            q.pop();
            for (auto v : g[u]) if (dist[v] > dist[u] + 1){
                dist[v] = dist[u] + 1; 
                q.push(v); 
            }
        }
        ll tmp = 0; 
        for (int j = 0;j < N;j ++) if (tmp < res) {
            tmp += dist[j];
        }
        res = min(res, tmp);
    }
    cout << res << "\n";
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...