[BOJ] 게임 개발

#include <iostream>
#include <queue>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;

vector<vector<int>> v;
int cost[501];
int idg[501]; // idg is indegree
int cost_dp[501];
int main(){
    int n;
    cin >> n;
    v.resize(n+1);
    
    for(int i=1; i<=n; i++){
        int value;
        cin >> value;
        cost[i] = value;
        while (1) {
            int a;
            scanf("%d",&a);
            if( a == -1 ) break;
            v[a].push_back(i);
            idg[i] ++;
        }
    }
    
    queue<int> q;
    for(int i=1; i<=n; i++){
        if( idg[i] == 0){
            q.push(i);
            cost_dp[i] = cost[i];
        }
    }
    
    while (! q.empty()) {
        int top = q.front();
        q.pop();
        
        int size = (int) v[top].size();
        for(int i=0; i<size; i++){
            int next = v[top][i];
            
            if( cost_dp[next] < cost_dp[top] + cost[next])
                cost_dp[next] = cost_dp[top] + cost[next];
    
            if ( --idg[next] == 0 )
                q.push(next);
        }
    }
    
    for(int i=1; i<=n; i++){
        printf("%d\n",cost_dp[i]);
    }
    
    return 0;
}