BOJ 1005 ACM Craft

www.acmicpc.net/problem/1005

1005번: ACM Craft

 

위상 정렬 + DP 문제였다.

1번 노드에서 걸리는 작업을 모두 완료하고 2번과 3번 노드에서 작업을 시작할 수 있다.

2번 노드에서 걸리는 시간은 1초이지만, 3번 노드에서 걸리는 시간이 100 초기 때문에

4번 노드에서 작업을 시작하려면 1번 10초 + 3번 100초 가 걸리고

4번노드까지 마치면 120초가 정답이 된다.

 

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
 
inline int max(int x, int y) { return x > y ? x : y; }
int tc, n, m, u, v, w;
int val[1001], res[1001], deg[1001];
 
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
 
    cin >> tc;
    while (tc--) {
        vector<int> a[1001];
        queue<int> q;
        fill(deg, deg + 1001, 0);
        fill(res, res + 1001, 0);
 
        cin >> n >> m;
        for (int i = 0; i < n; ++i) cin >> val[i];
 
        for (int i = 0; i < m; ++i) {
            cin >> u >> v;
            a[u - 1].push_back(v - 1);
            deg[v - 1]++;
        }
        cin >> w;
 
        for (int i = 0; i < n; ++i)
            if (!deg[i]) res[i] = val[i], q.push(i);
 
        for (int i = 0; i < n; ++i) {
            int cur = q.front(); q.pop();
            for (int nxt : a[cur]) {
                res[nxt] = max(res[nxt], val[nxt] + res[cur]);
                if (--deg[nxt] == 0) q.push(nxt);
            }
        }
        
        cout << res[w - 1] << '\n';
    }
 
    return 0;
}

 

31번 줄에서 차수가 0인 노드라면 자기 자신의 시간을 가져야 하니 담아주고,

36번째 줄에서 자기 자신과, 그 이전까지의 합 중에서 큰 것을 가져온다.