1516번

1516번 - 게임 개발

위상 정렬을 이용한 문제. 

2056번 (작업) 이랑 완전 똑같은 문제다.

<정답 코드>

#include<iostream>
#include<vector>
#include<queue>
 
using namespace std;
 
int indegree[501];
int dist[501];
int t[501];
int main()
{
    int n;
    vector<int> v[501];
    scanf("%d", &n);
 
    for (int i = 1; i <= n; i++)
    {
        int a;
        scanf("%d", &a);
        t[i] = a;
        while (scanf("%d",&a) && a != -1)
        {
            v[a].push_back(i);
            indegree[i]++;
        }
    }
 
    queue<int> q;
 
    for (int i = 1; i <= n; i++)
    {
        if (indegree[i] == 0)
        {
            q.push(i);
            dist[i] = t[i];
        }
    }
    
    while (!q.empty())
    {
        int now = q.front();
        q.pop();
 
        for (int i = 0; i < v[now].size(); i++)
        {
            int next = v[now][i];
            dist[next] = max(dist[next], dist[now] + t[next]);
            indegree[next]--;
 
            if (indegree[next] == 0)
            {
                q.push(next);
            }
        }
    }
 
    for (int i = 1; i <= n; i++)
    {
        printf("%d\n", dist[i]);
    }
    return 0;
}