백준[1005] ACM Craft

문제 설명

문제 링크

https://www.acmicpc.net/problem/1005

풀이

위상 정렬과 dp를 이용하여 풀이할 수 있다.

위상 정렬을 이용하여  순서를 찾는 과정에서 dp[nxt] = max(dp[nxt], dp[cur] + dp[nxt])로 특정 노드를 짓기 위한 최소 시간을 구할 수 있다.

코드

#include <cstdio>
#include <vector>
#include <cstring>
#include <queue>
#include <algorithm>

using namespace std;

int cnt[1003], dp[1003], cost[1003];

void solve() {
    memset(cnt, 0, sizeof cnt);
    memset(dp, 0, sizeof dp);
    memset(cost, 0, sizeof cost);
    int n, k; scanf("%d %d", &n, &k);
    vector<int> v[1003];
    for (int i = 1; i <= n; i++) scanf("%d", cost + i);
    for (int i = 0; i < k; i++) {
        int x, y; scanf("%d %d", &x, &y);
        v[x].push_back(y);
        cnt[y]++;
    }
    int w; scanf("%d", &w);
    queue<int> q;
    for (int i = 1; i <= n; i++) {
        if (!cnt[i]) q.push(i);
    }
    while (cnt[w] > 0) {
        int cur = q.front();
        q.pop();
        for (auto nxt : v[cur]) {
            dp[nxt] = max(dp[nxt], dp[cur] + cost[cur]);
            if (--cnt[nxt] == 0) q.push(nxt);
        }
    }
    printf("%d\n", dp[w] + cost[w]); // 마지막 노드 짓는 것까지 고려해야함
}

int main() {
    int t; scanf("%d", &t);
    while (t--) solve();
}