제출 #1325610

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1325610		pramad712	Bosses (BOI16_bosses)	C++17	100 / 100	452 ms	724 KiB

bosses

#include <bits/stdc++.h>
using namespace std;

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

    int node_count;
    cin >> node_count;

    vector<vector<int>> preferred_subordinates(node_count + 1);

    for (int node = 1; node <= node_count; node++) {
        int boss_count;
        cin >> boss_count;

        for (int index = 0; index < boss_count; index++) {
            int boss;
            cin >> boss;

            preferred_subordinates[boss].push_back(node);
        }
    }

    long long best = INT32_MAX;

    for (int root = 1; root <= node_count; root++) {
        vector distances(node_count + 1, INT32_MAX);
        distances[root] = 1;

        queue<pair<int, int>> bfs;
        bfs.emplace(root, 1);

        while (!bfs.empty()) {
            auto [node, distance] = bfs.front();
            bfs.pop();

            for (int subordinate: preferred_subordinates[node]) {
                if (distance + 1 < distances[subordinate]) {
                    distances[subordinate] = distance + 1;
                    bfs.emplace(subordinate, distance + 1);
                }
            }
        }

        best = min(best, accumulate(distances.begin() + 1, distances.end(), 0LL));
    }

    cout << best << "\n";
    return 0;
}

• Subtask 1: 22 / 22
• Subtask 2: 45 / 45
• Subtask 3: 33 / 33