Submission #1224264

#TimeUsernameProblemLanguageResultExecution timeMemory
1224264i_love_springBosses (BOI16_bosses)C++20
100 / 100
392 ms756 KiB
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ar array
void solve() {
  int n;
  cin >> n;
  vector<vector<int>> g(n);
  for (int i = 0; i < n;i++) {
    int k;cin >> k;
    for (int j = 0; j < k;j++) {
      int x;
      cin >> x;
      --x;
      g[x].push_back(i);
    }
  } 
  ll ans = 1e9+5;
  for (int i = 0; i < n;i++) {
    vector<ll>d(n,1e9);
    queue<int> q;
    q.push(i);
    d[i] = 1;
    while (!q.empty()) {
      auto u = q.front();
      q.pop();
      for(int v : g[u]) {
        if (d[v] > d[u] + 1) d[v] = d[u] + 1,q.push(v);
      }
    }
    ll cur = accumulate(d.begin(),d.end(),0ll);
    ans = min(ans,cur);
  }
  cout << ans;
}
signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  int t = 1;
  //cin >> t;
  while (t--) {
    solve();
    cout << "\n";
  }
  return 0;
} 
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...