제출 #973270

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
973270		jadai007	Bosses (BOI16_bosses)	C++17	100 / 100	586 ms	800 KiB

bosses

#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;
}

• Subtask 1: 22 / 22
• Subtask 2: 45 / 45
• Subtask 3: 33 / 33