#include <bits/stdc++.h>
using namespace std;
int N;
vector<int> adjList[5001];
int bfs(int root) {
vector<bool> seen(N+1);
queue<pair<int, int>> q; // node, depth
q.push({root, 1}); // starting depth at one
int ans = 0;
int reached = 0;
while (!q.empty()) {
pair<int, int> cur = q.front();
int u = cur.first;
int depth = cur.second;
q.pop();
if (!seen[u]) {
seen[u] = true;
reached++;
ans += depth;
for (auto v: adjList[u]) {
if (!seen[v]) {
q.push({v, depth+1});
}
}
}
}
if (reached < N) {
return INT_MAX;
}
return ans;
}
int main() {
cin >> N;
for (int v = 1; v <= N; v++) {
int k;
cin >> k;
for (int i = 0; i < k; i++) {
int u;
cin >> u;
adjList[u].push_back(v);
}
}
int ans = INT_MAX;
for (int i = 1; i <= N; i++) {
ans = min(ans, bfs(i));
}
cout << ans << "\n";
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
420 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
420 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
420 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
23 ms |
648 KB |
Output is correct |
13 |
Correct |
16 ms |
572 KB |
Output is correct |
14 |
Correct |
141 ms |
512 KB |
Output is correct |
15 |
Correct |
4 ms |
432 KB |
Output is correct |
16 |
Correct |
546 ms |
604 KB |
Output is correct |
17 |
Correct |
681 ms |
624 KB |
Output is correct |
18 |
Correct |
685 ms |
720 KB |
Output is correct |