제출 #531316

#제출 시각아이디문제언어결과실행 시간메모리
531316bonkBosses (BOI16_bosses)C++14
100 / 100
706 ms648 KiB
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int N = 5002;
vector<int>v[N];
int n;

ll ans = 1e18;

void bfs(int s){
    vector<bool>vis(N, 0);
    queue<pair<int, int>>q;
    vis[s] = true;
    q.emplace(s, 1);

    int cnt = 1;
    ll total = 0;

    while(!q.empty()){
        auto now = q.front(); q.pop();

        total += now.second;

        for(auto x: v[now.first]){
            if(!vis[x]){
                cnt++;
                vis[x] = true;
                q.emplace(x, now.second + 1);
            }
        }
    }

    if(cnt == n) ans = min(ans, total);
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n;

    for(int i = 1; i <= n; i++){
        int k; cin >> k;
        while(k--){
            int x; cin >> x;
            v[x].push_back(i);
        }
    }
    
    for(int i = 1; i <= n; i++)
        bfs(i);

    cout << ans << endl;

    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...