제출 #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...