제출 #79519

#제출 시각아이디문제언어결과실행 시간메모리
79519VinhspmBosses (BOI16_bosses)C++14
100 / 100
718 ms996 KiB
#include<bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define pb push_back

typedef pair<int, int> ii;

const int N = 5005;
const int oo = 1e9;

int n, ans = oo;
bool visit[N];
vector<int> vi[N];

void solve(int root)    {
    int sum = 0;
    memset(visit, false, sizeof visit);
    queue<ii> pq; pq.push(ii(root, 1));
    visit[root] = true;
    while(!pq.empty())  {
        ii cur = pq.front();
        pq.pop();
        sum += cur.se;
        for(int v: vi[cur.fi])  if(!visit[v]){
            visit[v] = true;
            pq.push(ii(v, cur.se + 1));
        }
    }
    for(int i = 1; i <= n; ++i) if(!visit[i]) return;
    ans = min(ans, sum);
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> n;
    for(int i = 1; i <= n; ++i) {
        int x; cin >> x;
        for(int j = 1; j <= x; ++j) {
            int u; cin >> u;
            vi[u].pb(i);
        }
    }
    for(int i = 1; i <= n; ++i) solve(i);
    cout << ans;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...