fork download
  1. #include <iostream>
  2. #include <vector>
  3. #include <queue>
  4.  
  5. using namespace std;
  6.  
  7. const int INF = 1e9;
  8.  
  9. int main() {
  10. ios_base::sync_with_stdio(false);
  11. cin.tie(NULL);
  12.  
  13. int n;
  14. cin>>n;
  15.  
  16. vector<vector<int>> adj(n + 2);
  17. for (int i = 1; i <= n; ++i) {
  18. int sd;
  19. cin >> sd;
  20. for (int j = 0; j < sd; ++j) {
  21. int az;
  22. cin >> az;
  23. adj[az].push_back(i);
  24. }
  25. }
  26.  
  27. long long mini = -1;
  28.  
  29. for (int i = 1; i <= n; ++i) {
  30. vector<int> dist(n + 1, INF);
  31. queue<int> q;
  32.  
  33. dist[i] = 0;
  34. q.push(i);
  35.  
  36. bool moz = true;
  37. long long ob = 0;
  38.  
  39. while (!q.empty()) {
  40. int u = q.front();
  41. q.pop();
  42.  
  43. ob += dist[u] + 1;
  44.  
  45. for (int v : adj[u]) {
  46. if (dist[v] == INF) {
  47. dist[v] = dist[u] + 1;
  48. q.push(v);
  49. }
  50. }
  51. }
  52.  
  53. for (int j = 1; j <= n; ++j) {
  54. if (dist[j] == INF) {
  55. moz = false;
  56. break;
  57. }
  58. }
  59.  
  60. if (moz==true) {
  61. if (mini == -1 || ob < mini) {
  62. mini = ob;
  63. }
  64. }
  65. }
  66.  
  67. cout << mini;
  68.  
  69. return 0;
  70. }
Success #stdin #stdout 0s 5324KB
stdin
4
1 4
3 1 3 4
2 1 2
1 3
stdout
8