#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define ff first
#define ss second
#define tri array<int,3>
const int inf = 1e18;
const int mod = 1e9+7;
const int mxn = 1e6 + 1;
int exp(int x, int n)
{
int res = 1;
for (; n > 0; res = (n % 2 ? res * x % mod : res), x = x * x % mod, n /= 2)
;
return res;
}
int inv(int x)
{
return exp(x, mod - 2);
}
void solve()
{
int n;
cin >> n;
vector<vector<int>> graph(n);
for(int i = 0; i < n; i++)
{
int sz;
cin >> sz;
while(sz--)
{
int a;
cin >> a;
graph[--a].push_back(i);
}
}
int mini = inf;
for(int rt = 0;rt < n; rt++)
{
queue<pii> bfs;
vector<vector<int>> tree(n);
vector<int> vis(n,0);
bfs.push({rt,rt});
vector<int> dp(n,inf);
dp[rt] = 1;
while(bfs.size())
{
pii cur =bfs.front();
bfs.pop();
if(vis[cur.ff])continue;
vis[cur.ff] = 1;
for(int a : graph[cur.ff])
bfs.push({a,cur.ff}),dp[a]=min(dp[a],dp[cur.ff]+1);
}
int sum = 0;
for(int i = 0; i < n; i++)
{
if(sum>inf)
break;
sum+=dp[i];
}
mini =min(mini,sum);
}
cout << mini << '\n';
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
srand(time(0));
int t = 1;
//cin >>t;
while (t--)
solve();
return 0;
}
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |