제출 #982143

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
982143		aaaaaarroz	Bosses (BOI16_bosses)	C++17	100 / 100	440 ms	832 KiB

bosses

#include <bits/stdc++.h>
    using namespace std;
    #define ll long long
    #define f first
    #define s second
    #define pb push_back
    #define pi pair<int,int>
    #define pl pair<ll,int>
     
    const int MAX = 5001;
     
    int color[MAX];
    ll dis[MAX];
    vector<int>g[MAX];
     
    int n;
     
    ll bfs(int u){
        fill(dis+1,dis+1+n, LLONG_MAX);
            dis[u] =1;
    	memset(color,0,sizeof(color));
        queue<int>q;
        q.push(u);
        while(!q.empty()){
            int from = q.front();
            q.pop();
           if(color[from]) continue;
            color[from]=1;
            for(int to: g[from]){
                if(dis[to]>dis[from]+1){
                    dis[to]= dis[from]+1;
                    q.push(to);
                }
            }
        }
        
        ll sum = 0;
        for(int i = 1; i <=n; i++) {
            sum+= dis[i];
            if(dis[i]==LLONG_MAX) return LLONG_MAX;
        }
      //  cout << endl << sum << "  "<< u << endl;
     //   cout << u << " "<< sum << endl;
        return sum;
    }
     
     
    int main(){
        ios_base::sync_with_stdio(0);
        cin.tie(0); cout.tie(0);
        cin >> n;
        
        int temp, k;
        for(int i = 1; i <= n; i++){
            cin >> temp;
            while(temp--){
                cin >> k;
                g[k].pb(i);
            }
        }
     
        ll ans= LLONG_MAX;
        for(int i= 1; i <= n; i++){
            ans = min(bfs(i),ans);
        }
        cout << ans << endl;
    }

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