1516 게임개발

#include <stdio.h>
#include <queue>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int cost[600] = { 0 };
int indegree[600] = { 0 };
int rst[600] = { 0 };
vector<vector<int> > adj(600);
queue<int> q;
 
int main() {
    int n;
    scanf("%d", &n);
 
    for (int i = 1; i <= n; i++) {
        scanf("%d", &cost[i]);
        while (1) {
            int num;
            scanf("%d", &num);
 
            if (num == -1)
                break;
 
            indegree[i]++;
            adj[num].push_back(i);
        }
    }
 
    for (int i = 1; i <= n; i++)
        if (indegree[i] == 0) {
            q.push(i);
            rst[i] = cost[i];
        }
            
 
    while (q.empty() == false) {
        int x = q.front();        
        q.pop();
 
        for (int i = 0; i < adj[x].size(); i++) {
            indegree[adj[x][i]]--;
            rst[adj[x][i]] = max(rst[adj[x][i]], 
                rst[x]+cost[adj[x][i]]);
 
            if(indegree[adj[x][i]] == 0)
                q.push(adj[x][i]);
        }
    }
 
    for (int i = 1; i <= n; i++)
        printf("%d\n", rst[i]);
}