제출 #1281066

#제출 시각아이디문제언어결과실행 시간메모리
1281066david_g611Bosses (BOI16_bosses)C++20
100 / 100
451 ms728 KiB
#include <bits/stdc++.h>
#define int long long
using namespace std;

const int NMAX=5000;
int n, ans=1e9;
bool viz[NMAX+1];

vector<int> g[NMAX+1];
void bfs(int nod)
{
    int now_ans=0;
    queue<pair<int, int>> q;
    q.push({nod, 1});
    viz[nod]=1;
    while(q.size())
    {
        auto &[p, d]=q.front();
        q.pop();
        now_ans+=d;
        for(auto &vecin:g[p])
            if(!viz[vecin])
            {
                viz[vecin]=1;
                q.push({vecin, d+1});
            }
    }
    for(int i=1; i<=n; i++)
        if(!viz[i])
            return;
    ans=min(ans, now_ans);
}
signed main()
{
    cin>>n;
    for(int i=1, cati, x; i<=n; i++)
    {
        cin>>cati;
        while(cati--)
        {
            cin>>x;
            g[x].push_back(i);
        }
    }

    for(int i=1; i<=n; i++)
    {
        for(auto &x:viz)x=0;
        bfs(i);
    }
    cout<<ans;
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...