백준 1516번: 게임 개발 - 위상정렬 dp C++ 코드

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

1516번: 게임 개발

#include <bits/stdc++.h>

using namespace std;

int n, m;
int degree[1001];
vector<int> adj[1001];
int cost[501];
int res[501];
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
   
    cin >> n;
    for (int i = 1; i <= n; i++) {
        int t;
        cin >> t;
        cost[i] = t;

        int a;
        while (1) {
            cin >> a;
            if (a == -1) break;
            adj[a].push_back(i);
            degree[i]++;
        }
    }
    

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

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

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

    for (int i = 1; i <= n; i++) {
        cout << res[i] << '\n';
    }


    return 0;
}

백준 1516번

위상정렬 다이나믹프로그래밍 문제