제출 #695095

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

const int N = 5001;
vector<int> g[N];

int cnt;
long long tmp;
int cost[N];
inline void bfs(int v, int d = 1) {
  queue<int> q; 
  tmp = cnt = 0; 
  memset(cost, -1, sizeof cost);
  cost[v] = 1; 
  q.push(v);
  while(!q.empty()) {
    cnt++;
    int src = q.front();
    tmp += cost[src];
    q.pop();
    for (int u : g[src]) {
      if (cost[u] == -1) {
        cost[u] = cost[src] + 1; 
        q.push(u);
      }
    }
  }
}

signed main() {
  int n;
  cin >> n;
  for (int i = 1; i <= n; ++i) {
    int k;
    cin >> k;
    for (int j = 0; j < k; ++j) {
      int x;
      cin >> x;
      g[x].push_back(i);
    }
  }
  long long ans = LLONG_MAX / 3; 
  for (int i = 1; i <= n; ++i) {
    bfs(i);
   if (cnt == n) {
      ans = min(ans, tmp);
   }
  }
  cout << ans << '\n';
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...