#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int maxN = 5005;
const int INF = 1e9 + 5;
int n;
vector<int> adj[maxN];
vector<bool> visited(maxN);
int bfs(int root) {
for(int i = 0; i <= n; i++) {
visited[i] = false;
}
queue<pair<int, int>> q;
q.push({root, 1});
visited[root] = true;
ll cost = 0;
while(!q.empty()) {
auto v = q.front();
q.pop();
cost += v.second;
for(int u : adj[v.first]) {
if (!visited[u]) {
visited[u] = true;
q.push({u, v.second+1});
}
}
}
if (count(visited.begin(), visited.end(), true) != n) return INF;
return cost;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
for(int ord = 1; ord <= n; ord++) {
int k;
cin >> k;
for(int j = 0; j < k; j++) {
int boss;
cin >> boss;
adj[boss].push_back(ord);
}
}
int best = INF;
// root the tree at every possible vertex
for(int boss = 1; boss <= n; boss++) {
best = min(best, bfs(boss));
}
cout << best;
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
492 KB |
Output is correct |
2 |
Correct |
1 ms |
512 KB |
Output is correct |
3 |
Correct |
1 ms |
492 KB |
Output is correct |
4 |
Correct |
1 ms |
492 KB |
Output is correct |
5 |
Correct |
1 ms |
492 KB |
Output is correct |
6 |
Correct |
1 ms |
492 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
492 KB |
Output is correct |
2 |
Correct |
1 ms |
512 KB |
Output is correct |
3 |
Correct |
1 ms |
492 KB |
Output is correct |
4 |
Correct |
1 ms |
492 KB |
Output is correct |
5 |
Correct |
1 ms |
492 KB |
Output is correct |
6 |
Correct |
1 ms |
492 KB |
Output is correct |
7 |
Correct |
1 ms |
492 KB |
Output is correct |
8 |
Correct |
1 ms |
492 KB |
Output is correct |
9 |
Correct |
1 ms |
492 KB |
Output is correct |
10 |
Correct |
1 ms |
492 KB |
Output is correct |
11 |
Correct |
1 ms |
492 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
492 KB |
Output is correct |
2 |
Correct |
1 ms |
512 KB |
Output is correct |
3 |
Correct |
1 ms |
492 KB |
Output is correct |
4 |
Correct |
1 ms |
492 KB |
Output is correct |
5 |
Correct |
1 ms |
492 KB |
Output is correct |
6 |
Correct |
1 ms |
492 KB |
Output is correct |
7 |
Correct |
1 ms |
492 KB |
Output is correct |
8 |
Correct |
1 ms |
492 KB |
Output is correct |
9 |
Correct |
1 ms |
492 KB |
Output is correct |
10 |
Correct |
1 ms |
492 KB |
Output is correct |
11 |
Correct |
1 ms |
492 KB |
Output is correct |
12 |
Correct |
7 ms |
512 KB |
Output is correct |
13 |
Correct |
5 ms |
492 KB |
Output is correct |
14 |
Correct |
268 ms |
620 KB |
Output is correct |
15 |
Correct |
88 ms |
492 KB |
Output is correct |
16 |
Correct |
754 ms |
664 KB |
Output is correct |
17 |
Correct |
876 ms |
620 KB |
Output is correct |
18 |
Correct |
971 ms |
748 KB |
Output is correct |