[BOJ-1516]게임개발

위상정렬 문제 ACM-craft 문제와 비슷한거 같다.

들어오는 경로를 back_edge로 그어주고, 나가는 경로를 edge 로 구성한다.

나가는 경로에 존재하는 정점의 차수를 +1 시키고 

위상정렬을 그대로 돌리면 된다. 

이때 큐에서 꺼내어 만들어지는 시간을 비교할 때 보다 큰 값이 있을 때 갱신을 시키면 되는 문제이다.

#include<cstdio>
#include<vector>
#include<queue>
using namespace std;
 
typedef vector<int> VI;
 
VI deg;
VI edge[555];
VI back_edge[555];
VI build_time;
VI result;
int main(){
    int n;
    scanf("%d", &n);
    deg = VI(n+1, 0);
    build_time = VI(n+1, 0);
    result = VI(n+1, 0);
    for(int build = 1 ; build <= n ; build++){
        int time;
        scanf("%d", &time);
        build_time[build] = time;
        while(true){
            int pre;
            scanf("%d",&pre);
            if(pre==-1) break;
            edge[pre].push_back(build);
            back_edge[build].push_back(pre);
            deg[build]++;
        }
    } // end input
 
    queue<int> Q;
    for(int i = 1 ; i <= n ; i++){
        if(deg[i] == 0){
            Q.push(i);
            result[i] = build_time[i];
        }
    } // set result = build_time if deg == 0
 
    while(!Q.empty()){
        int here = Q.front(); Q.pop();
        
        for(auto iter = back_edge[here].begin() ; iter != back_edge[here].end() ; iter++){
            int pre = *iter;
            if( result[here] < result[pre] + build_time[here]){
                result[here] = result[pre] + build_time[here];
            }
        }
 
        for(auto iter = edge[here].begin() ; iter != edge[here].end() ; iter++){
            int there = *iter;
            deg[there]--;
            if(deg[there] == 0){
                Q.push(there);
            }
        }
    }
 
    for(int build = 1 ; build <= n ; build++){
        printf("%d\n", result[build]);
    }
    return 0;
}