제출 #857766

#제출 시각아이디문제언어결과실행 시간메모리
857766qrnoBosses (BOI16_bosses)C++17
100 / 100
420 ms748 KiB
#include <bits/stdc++.h>
using namespace std;

const int INF = 1e9;
const int MAXN = 5e3;

int best = INF;

int N;
array<vector<int>, MAXN> G;
array<int, MAXN> val, last;

signed main() {
  ios::sync_with_stdio(false); cin.tie(nullptr);

  cin >> N;
  for (int i = 0; i < N; i++) {
    int K; cin >> K;
    while (K--) {
      int u; cin >> u; u--;
      G[u].push_back(i);
    }
  }

  for (int i = 0; i < N; i++) {
    queue<int> Q;
    Q.push(i);
    val[i] = 1;
    last[i] = i;

    int done = 0, sum = 0;
    while (!Q.empty()) {
      auto v = Q.front(); Q.pop();
      sum += val[v];
      if (sum >= best) break;
      done++;
      for (auto u : G[v]) {
        if (last[u] != i) {
          Q.push(u);
          val[u] = val[v]+1;
          last[u] = i;
        }
      }
    }

    if (done < N) continue;
    best = min(best, sum);
  }
  cout << best << endl;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...