제출 #408828

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

#define fi first
#define se second

typedef long long ll;
typedef pair<int,int> ii;

const int N = 5e3;
const int INF = 1e9;
int n;
int dis[N+2];
vector<int> lst[N+2];

int bfs(int st) {
    for (int i = 1; i <= n; i++) dis[i] = -1;
    queue<int> q;
    q.push(st); dis[st] = 0;
    while (!q.empty()) {
        int cur = q.front(); q.pop();
        for (int nx : lst[cur]) {
            if (dis[nx] != -1) continue;
            dis[nx] = dis[cur]+1;
            q.push(nx);
        }
    }
    int ret = n;
    for (int i = 1; i <= n; i++) {
        if (dis[i] == -1) return INF;
        ret += dis[i];
    }
    return ret;
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        int k; cin >> k;
        for (int j = 1; j <= k; j++) {
            int x; cin >> x;
            lst[x].push_back(i);
        }
    }
    int ans = INF;
    for (int i = 1; i <= n; i++) {
        ans = min(ans,bfs(i));
    }
    cout << ans << '\n';
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...