제출 #1279780

#제출 시각아이디문제언어결과실행 시간메모리
1279780SSKMFBosses (BOI16_bosses)C++20
0 / 100
1 ms572 KiB
#include <bits/stdc++.h>
using namespace std;

vector <int> adiacenta[5001];
int distanta[5001] , moment[5001];

int main ()
{
    ios :: sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    int numar_noduri;
    cin >> numar_noduri;

    for (int nod = 1 ; nod <= numar_noduri ; nod++)
    {
        int grad;
        cin >> grad;

        while (grad--)
        {
            int sursa; cin >> sursa;
            adiacenta[sursa].push_back(nod);
        }
    }

    int minim = INT32_MAX;
    for (int radacina = 1 ; radacina <= numar_noduri ; radacina++)
    {
        int suma = 1;
        distanta[radacina] = 1;
        moment[radacina] = radacina;
        queue <int> candidati; candidati.push(radacina);
        while (!candidati.empty())
        {
            const int nod = candidati.front();
            candidati.pop();

            for (auto& vecin : adiacenta[nod]) {
                if (moment[vecin] != radacina)
                {
                    moment[vecin] = radacina;
                    distanta[vecin] = distanta[nod] + 1;
                    suma += distanta[vecin];
                    candidati.push(vecin);
                }
            }
        }

        minim = min(minim , suma);
    }

    cout << minim;
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...