제출 #796758

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
796758		exodus_	Bosses (BOI16_bosses)	C++14	100 / 100	395 ms	628 KiB

bosses

#include<bits/stdc++.h>
using namespace std;
vector<int>adje[5005];
bool vis[5005];
long long biy;
int ct;
void BFS(int x) {
    queue<pair<int,int>> q;
    q.push({x, 1});
    vis[x]=true;
    while(!q.empty()) {
        int node = q.front().first;
        int ting = q.front().second;
        q.pop();
        biy+=(ting*1ll);
        ct++;
        for (auto itr:adje[node]) {
            if(vis[itr]) continue;
            vis[itr]=true;
            q.push({itr, ting+1});
        }
    }
}
int main() {
    int N, t, a;
    cin >> N;
    for (int i=1; i<=N; i++) {
        cin >> t;
        for (int j=1; j<=t; j++) {
            cin >> a;
            adje[a].push_back(i);
        }
    }
    long long jawab = 1e18;
    for (int i=1; i<=N; i++) {
        ct = 0;
        biy = 0;
        memset(vis, 0, sizeof(vis));
        BFS(i);
        if(ct!=N) continue;
        jawab = min(jawab, biy);
    }
    cout << jawab << endl;
    return 0;
}

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