제출 #790902

#제출 시각아이디문제언어결과실행 시간메모리
790902makanhuliaBosses (BOI16_bosses)C++17
100 / 100
399 ms668 KiB
#include<bits/stdc++.h>
using namespace std;
#define ioss ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define tup tuple<int, int, int>
#define pii pair<int, int>
#define fi first
#define se second
#define pub push_back
#define pob pop_back
int n;
vector<int> adj[5004];
bool vis[5004];
int dist[5004];
queue<int> q;
int main() {
    ioss;
    cin >> n;
    for(int i = 1; i <= n; i++) {
        int k; cin >> k;
        for(int j = 0; j < k; j++) {
            int a; cin >> a;
            adj[a].pub(i);
        }
    }
    int ans = 1e9;
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= n; j++) vis[j] = 0, dist[j] = 0;
        dist[i] = 1, vis[i] = 1;
        q.push(i);
        while(!q.empty()) {
            int u = q.front();
            q.pop();
            for(auto v : adj[u]) {
                if(!vis[v]) {
                    vis[v] = 1;
                    dist[v] = dist[u]+1;
                    q.push(v);
                }
            }
        }
        int cur = 0;
        bool notvis = 0;
        for(int j = 1; j <= n; j++) {
            if(!vis[j]) {
                notvis = 1;
                break;
            }
            cur += dist[j];
        }
        if(notvis) continue;
        ans = min(ans, cur);
        // cout << " root " << i << " " << cur << " " << ans << endl; 
    }
    cout << ans << endl;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...