작업 (feat. 백준, 2056번)

작업
https://www.acmicpc.net/problem/2056

2056번: 작업

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#include <math.h>
using namespace std;
vector<int> arr[10001];
int check[10001]{0};
int time[10001]{0}, ans[10001]{0};
int main() {
	ios::sync_with_stdio(false), cin.tie(NULL);
    register int N, total = 0;
    cin >> N;
    for(register int n = 1, b; n <= N; ++n){
        cin >> time[n] >> b, ans[n] = time[n];
        for(register int i = 0, v; i < b; ++i){
            cin >> v;
            arr[v].push_back(n);
            ++check[n];
        }
    }
    priority_queue<int, vector<int>, greater<int>> q;
    for(register int n = 1; n <= N; ++n)
        if(!check[n])
            q.push(n);
    while(!q.empty()){
        auto pos = q.top(); q.pop();
        total = max(total, ans[pos]);
        for(auto& v : arr[pos]){
            ans[v] = max(ans[v], ans[pos] + time[v]);
            if(--check[v] == 0)
                q.push(v);
        }
    }
    cout << total;
	return 0;
}
// *&)*@*

 

반응형

위상 정렬을 이용하는 문제입니다.

각 작업 번호마다의 시간을 누적하여 풀이하면 됩니다.