제출 #857758

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

#define int long long
#define all(v) begin(v), end(v)

int N;
vector<vector<int>> G;

int bfs(int v) {
  vector<int> val(N, -1);
  queue<pair<int, int>> Q;
  val[v] = 1;
  Q.push({v, val[v]});

  while (!Q.empty()) {
    auto [v, x] = Q.front(); Q.pop();
    for (auto u : G[v]) {
      if (val[u] == -1) {
        val[u] = x+1;
        Q.push({u, val[u]});
      }
    }
  }

  if (*min_element(all(val)) == -1) return -1;
  return accumulate(all(val), 0LL);
}

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

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

  int best = -1;
  for (int i = 0; i < N; i++) {
    int sum = bfs(i);
    if (best == -1 || best > sum)
      best = sum;
  }
  cout << best << endl;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...