Submission #1152789

#TimeUsernameProblemLanguageResultExecution timeMemory
1152789tegsheeBosses (BOI16_bosses)C++20
100 / 100
400 ms3012 KiB
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ss second
#define ff first
#define pb push_back
const int mxn=1e5+5; 
int n,res=1e12,d[mxn];
vector<int> g[mxn];
void bfs(int k) {
    for(int i=1; i<=n; i++)  d[i]=1e12;
    queue<int> q;
    q.push(k);
    d[k]=1;
    int u=0;
    while(!q.empty()) { 
        int x=q.front();
        q.pop();
        u+=d[x];
        for(int u:g[x]) {
            if(d[u]>d[x]+1) {
                d[u]=d[x]+1;
                q.push(u);
            }
        }
    }
    for(int i=1; i<=n; i++) {
        if(d[i]==1e12) u=1e12;
    }
    res=min(res,u);
} 
signed main () {
    ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
    cin>>n;
    for(int i=1; i<=n; i++) {
        int s;  
		cin>>s;
        while(s--) {
            int v;
            cin>>v;
            g[v].pb(i);
        }
    }
    for(int i=1; i<=n; i++)  bfs(i);
    cout<<res;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...