제출 #973270

#제출 시각아이디문제언어결과실행 시간메모리
973270jadai007Bosses (BOI16_bosses)C++17
100 / 100
586 ms800 KiB
#include<bits/stdc++.h>

using namespace std;

int n, vis[5050], k, u, ans = 1e9;
vector<int> vc[5050];
queue<pair<int, int>> q;

int main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    cin >> n;
    for(int i = 1; i<=n; ++i){
        cin >> k;
        while(k--){
            cin >> u;
            vc[u].emplace_back(i);
        }
    }
    for(int i = 1; i<=n; ++i){
        int sum = 0, node = 0;
        memset(vis, 0, sizeof(vis));
        q.emplace(i, 1);
        while(!q.empty()){
            int u = q.front().first, w = q.front().second; q.pop();
            if(vis[u]) continue;
            vis[u] = 1;
            ++node;
            sum+=w;
            for(auto v:vc[u]) if(!vis[v]) q.emplace(v, w+1);
        }
        //cout << node << ' ' << sum << '\n';
        if(node == n) ans = min(ans, sum);
    }
    cout << ans;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...