제출 #1153058

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1153058		AlgorithmWarrior	Bosses (BOI16_bosses)	C++20	100 / 100	367 ms	712 KiB

bosses

#include <bits/stdc++.h>

using namespace std;

int const INF=1e9;
int const MAX=5005;
int n;
vector<int>sons[MAX];

void read(){
    cin>>n;
    int i;
    for(i=1;i<=n;++i){
        int nr;
        cin>>nr;
        while(nr--){
            int boss;
            cin>>boss;
            sons[boss].push_back(i);
        }
    }
}

int cost[MAX];

int bfs(int start){
    int i;
    for(i=1;i<=n;++i)
        cost[i]=0;
    queue<int>q;
    cost[start]=1;
    q.push(start);
    while(!q.empty()){
        int curr=q.front();
        q.pop();
        for(auto fiu : sons[curr])
        if(!cost[fiu]){
            cost[fiu]=cost[curr]+1;
            q.push(fiu);
        }
    }
    bool gasit=0;
    int sum=0;
    for(i=1;i<=n;++i)
        if(cost[i])
            sum+=cost[i];
        else
            gasit=1;
    return ((gasit)?INF:sum);
}

void minself(int& x,int val){
    if(x>val)
        x=val;
}

int solve(){
    int minim=INF;
    int i;
    for(i=1;i<=n;++i)
        minself(minim,bfs(i));
    return minim;
}

int main()
{
    read();
    cout<<solve();
    return 0;
}

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