제출 #1338431

#제출 시각아이디문제언어결과실행 시간메모리
1338431orgiloogiiBosses (BOI16_bosses)C++20
0 / 100
0 ms344 KiB
#include <bits/stdc++.h>
#define int long long
#define ff first
#define ss second
using namespace std;
vector <int> vis;
// int dfs(int u) {
//     for (auto v : adj1[u]) {
//         if (vis[v] == true) continue;
//         vis[v] = true;
//         int x = dfs(v);
//         salar[u] += x;
//     }
//     return salar[u];
// }
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];
        ans = min(ans, sum);
    }
    cout << ans << endl;
    // cout << ans << endl;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...