Submission #938832

#	Time	Username	Problem	Language	Result	Execution time	Memory
938832		Darren0724	Bosses (BOI16_bosses)	C++17	100 / 100	429 ms	848 KiB

bosses

#include <bits/stdc++.h>
using namespace std;
#define LCBorz ios_base::sync_with_stdio(false); cin.tie(0);
#define all(x) x.begin(), x.end()
#define endl '\n'
const int N=5005;
const int INF=1e9;
int32_t main() {
    LCBorz;
    int n;cin>>n;
    vector<int> adj[N];
    for(int i=1;i<=n;i++){
        int k;cin>>k;
        for(int j=0;j<k;j++){
            int p;cin>>p;
            adj[p].push_back(i);
        }
    }
    auto bfs=[&](int s)->int {
        vector<int> dis(N,INF);
        queue<int> q;
        q.push(s);
        dis[s]=0;
        int ans=0,cnt=0;
        while(q.size()){
            int p=q.front();
            q.pop();
            ans+=dis[p];
            cnt++;
            for(int j:adj[p]){
                if(dis[j]==INF){
                    dis[j]=dis[p]+1;
                    q.push(j);
                }
            }
        }
        if(cnt==n)return ans+n;
        return INF;
    };
    int ans=INF;
    for(int i=1;i<=n;i++){
        ans=min(ans,bfs(i));
    }
    cout<<ans<<endl;
    return 0;
}

• Subtask 1: 22 / 22
• Subtask 2: 45 / 45
• Subtask 3: 33 / 33