백준 1516 게임 개발 혼내주기

 

위상정렬인데, 특정 건물을 짓기 전 소요되는 가장 긴 시간을 기준으로 완성 시간을 구해나가면 된다. 개인적으로 1766이나 2252번 보다 더 어려운 것 같은데 난이도가 더 낮아서 의아하다... 두 문제가 overrated된 느낌

 

#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(0), cin.tie(0)
using namespace std;

vector<int> adj[501];
int indegree[501], arr[501], cost[501];
int n;

void input() {
    fastio;
    cin >> n;
    for(int i = 1; i <= n; ++i) {
        cin >> arr[i];
        int req;
        while(cin >> req) {
            if(req == -1) break;
            ++indegree[i];
            adj[req].push_back(i);
        }
    }
}

int main() {
    input();

    queue<int> q;
    for(int i = 1; i <= n; ++i) {
        if(!indegree[i]){
            q.push(i);
            cost[i] = arr[i];
        }
    }
    
    while(!q.empty()) {
        int from = q.front(); q.pop();
        for(int to : adj[from]) {
            --indegree[to];
            cost[to] = max(cost[to], cost[from] + arr[to]);
            if(!indegree[to]) {
                q.push(to);
            }
        }
    }

    for(int i = 1; i <= n; ++i)
        cout << cost[i] << "\n";
}