Submission #891630

#TimeUsernameProblemLanguageResultExecution timeMemory
891630ind1vBosses (BOI16_bosses)C++11
100 / 100
412 ms796 KiB
#include <bits/stdc++.h>

using namespace std;

const int N = 5e3 + 5;

int n;
vector<int> g[N];
bool vis[N];
int lv[N];
int ans = 1e9;

void bfs(int u) {
  memset(lv, -1, sizeof(lv));
  lv[u] = 1;
  queue<int> q;
  q.push(u);
  while (!q.empty()) {
    int v = q.front();
    q.pop();
    for (int nxt : g[v]) {
      if (lv[nxt] == -1) {
        lv[nxt] = lv[v] + 1;
        q.push(nxt);
      }
    }
  }
  if (*min_element(lv + 1, lv + n + 1) > -1) {
    ans = min(ans, accumulate(lv + 1, lv + n + 1, 0));
  }
}

int main() {
  ios::sync_with_stdio(false);
  cin.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;
      g[x].emplace_back(i);
    }
  }
  for (int i = 1; i <= n; i++) {
    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...