제출 #986468

#제출 시각아이디문제언어결과실행 시간메모리
986468andrei_iorgulescuBosses (BOI16_bosses)C++14
100 / 100
446 ms768 KiB
#include <bits/stdc++.h> using namespace std; int n; vector<int> g[5005]; vector<int> bfs(int nod) { vector<int> d(n + 1); for (int i = 1; i <= n; i++) d[i] = -1; d[nod] = 0; queue<int> q; q.push(nod); while (!q.empty()) { int x = q.front(); q.pop(); for (auto vecin : g[x]) { if (d[vecin] == -1) { d[vecin] = 1 + d[x]; q.push(vecin); } } } return d; } int main() { 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].push_back(i); } } int ans = 1e9; for (int i = 1; i <= n; i++) { vector<int> d = bfs(i); bool cringe = false; for (int j = 1; j <= n; j++) if (d[j] == -1) cringe = true; if (!cringe) { int cur = 0; for (int j = 1; j <= n; j++) cur += d[j] + 1; ans = min(ans,cur); //cout << i << ' ' << cur << endl; } } cout << ans; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...