제출 #1338437

#제출 시각아이디문제언어결과실행 시간메모리
1338437orgiloogiiBosses (BOI16_bosses)C++20
100 / 100
451 ms776 KiB
#include <bits/stdc++.h>
#define int long long
#define ff first
#define ss second
using namespace std;
signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    int n;
    cin >> n;
    vector <vector <int>> adj1;
    adj1.assign(n + 1, {});
    for (int i = 1;i <= n;i++) {
        int k;
        cin >> k;
        for (int j = 0;j < k;j++) {
            int x;
            cin >> x;
            adj1[x].push_back(i);
        }
    }   
    // for (int i = 1;i <= n;i++) {
    //     cout << i << ": ";
    //     for (auto x : adj1[i]) {
    //         cout << x << " ";
    //     }
    //     cout << endl;
    // }
    int ans = INT_MAX;
    for (int i = 1;i <= n;i++) {
        queue <int> q;
        int sum = 0;
        q.push(i);
        vector <bool> vis(n + 1, 0);
        vector <int> salar(n + 1, 0);
        salar[i] = 1;
        vis[i] = 1;
        while (!q.empty()) {
            auto u = q.front();
            q.pop();
            for (auto v : adj1[u]) {
                if (!vis[v]) {
                    salar[v] = salar[u] + 1;
                    vis[v] = true;
                    q.push(v);
                }
            }
        }
        for (int i = 1;i <= n;i++) sum += salar[i];
        for (int i = 1;i <= n;i++) 
            if (vis[i] == false) sum = INT_MAX;
        ans = min(ans, sum);
        // cout << i << " " << sum << endl;
    }
    cout << ans << endl;
    // cout << ans << endl;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...