[BOJ/백준][Gold4] 2056 : 작업 (C++)

www.acmicpc.net/problem/2056

2056번: 작업

 

 

[난이도] Gold4

[유형] 위상정렬

 

[풀이]

위상정렬로 각 작업을 방문하면서 total 배열에 그 작업에 도착하기 까지의 시간을 기록하면 된다.

#include <cstdio>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
int N,work[10001],total[10001],in[10001],ret;
vector<int> adj[10001];
int main(){
    scanf("%d",&N);
    for(int i=1;i<=N;i++){
        int ac,pre;
        scanf("%d%d",&work[i],&ac);
        in[i] = ac;
        for(int j=0;j<ac;j++){
            scanf("%d",&pre);
            adj[pre].push_back(i);
        }
    }
    queue<int> q;
    for(int i=1;i<=N;i++) if(!in[i]) q.push(i);
    while(!q.empty()){
        int qf = q.front(); q.pop();
        ret = max(ret,total[qf]+work[qf]);
        for(auto nxt : adj[qf]){
            total[nxt] = max(total[nxt],total[qf]+work[qf]);
            if(--in[nxt]==0) q.push(nxt);
        }

    }   
    printf("%d",ret);
}

 

github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold4/2056.cpp