제출 #1295390

#제출 시각아이디문제언어결과실행 시간메모리
1295390Born_To_LaughBosses (BOI16_bosses)C++17
0 / 100
1 ms712 KiB
// Born_To_Laugh - Hughie Do
#include <bits/stdc++.h>
#define fi first
#define se second
#define alle(x) x.begin(), x.end()
using namespace std;
typedef long long ll;
typedef long double ld;
const ll INF = 1e9 + 7;
const int maxn = 5010;
int n;
vector<int> adj[maxn];
ll process(int x){
    vector<int> dist(maxn, INF);
    vector<int> vis(maxn, 0);
    dist[x] = 1;
    vis[x] = 1;
    ll ans = 0;
    
    deque<int> bfs;
    bfs.push_back(x);
    while(!bfs.empty()){
        int a = bfs.front();
        bfs.pop_front();
        ans += dist[a];
        
        for(auto &elm: adj[a]){
            if(vis[elm])continue;
            bfs.push_back(elm);
            vis[elm] = 1;
            dist[elm] = dist[a] + 1;
        }
    }
    return ans;
}
void solve(){
    cin >> n;
    for(int i=1; i<=n; ++i){
        int k;cin >> k;
        for(int j=1; j<=k; ++j){
            int x;cin >> x;
            adj[x].push_back(i);
        }
    }
    ll ans = INF;
    for(int i=1; i<=n; ++i){
        ans = min(ans, process(i));
    }
    cout << ans << '\n';
}
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int tt = 1;
    // cin >> tt;
    while(tt--){
        solve();
        // cleardata();
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...