Submission #1072860

#TimeUsernameProblemLanguageResultExecution timeMemory
1072860Jarif_RahmanBosses (BOI16_bosses)C++17
100 / 100
390 ms764 KiB
#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;

vector<int> bfs(const vector<vector<int>> &graph, int source){
    int n = graph.size();
    vector<int> dis(n, -1);
    queue<int> Q;
    dis[source] = 0;
    Q.push(source);
    
    while(!Q.empty()){
        int nd = Q.front();
        Q.pop();
        for(int x: graph[nd]) if(dis[x] == -1){
            dis[x] = dis[nd]+1;
            Q.push(x);
        }
    }

    return dis;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n; cin >> n;
    vector<vector<int>> graph(n);
    for(int i = 0; i < n; i++){
        int k; cin >> k;
        while(k--){
            int p; cin >> p; p--;
            graph[p].push_back(i);
        }
    }

    int ans = 1e9;
    for(int i = 0; i < n; i++){
        auto dis = bfs(graph, i);
        int cur = n;
        for(int x: dis){
            if(x == -1){
                cur = 1e9;
                break;
            }
            cur+=x;
        }
        ans = min(ans, cur);
    }

    cout << ans << "\n";
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...