딩코딩 : Computer Science 블로그

https://www.acmicpc.net/problem/2056

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

int n;
int cost[10003];
vector<int> adj[10003];
int degree[10003];
int res[10003];
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> cost[i];

        int k;
        cin >> k;
        for (int j = 0; j < k; j++) {
            int pre;
            cin >> pre;
            adj[pre].push_back(i);
            degree[i]++;
        }
    }

    int ans = 0;
    queue<int> Q;
    for (int i = 1; i <= n; i++) {
        if (degree[i] == 0) {
            res[i] = cost[i];
            Q.push(i);
            ans = max(res[i], ans);
        }
    }

    while (!Q.empty()) {
        int x = Q.front();
        Q.pop();

        for (auto nx : adj[x]) {
            res[nx] = max(res[nx], res[x] + cost[nx]);
            ans = max(ans, res[nx]);
            if (--degree[nx] == 0) {
                Q.push(nx);
            }
        }
    }


    cout << ans << '\n';
   
    return 0;
}