문제

[백준] ACM Craft (Gold 3)

요약

  • 모든 건물은 완성하는 데 걸리는 Delay가 존재한다.
  • 어떤 건물을 짓기 위해 먼저 지어야 하는 건물이 존재할 수 있다.
  • 여러 개의 건물을 동시에 지을 수 있다.
  • 특정 건물을 짓는다면 게임에서 승리한다고 할 때, 승리하기까지 걸리는 최소 시간을 알아내자.

분류

  • 위상 정렬
  • DP

풀이

1. 내 풀이 (위상 정렬 + DP)

  • 선행 건물이 모두 지어져야 특정 건물을 지을 수 있다 (위상 정렬)
  • 특정 건물이 지어지기까지 걸리는 시간은 (선행 건물들이 모두 완성될 때까지 걸리는 시간 + 특정 건물을 완성하기 위한 시간) 이다. 이는 연쇄적으로 계산된다. (DP)


from collections import deque
import sys
input = sys.stdin.readline

t = int(input())

for _ in range(t):
    n, m = map(int, input().split())
    weights = list(map(int, input().split()))
    cnts = [0] * n
    graph = [[] for _ in range(n)]

    for _ in range(m):
        a, b = map(int, input().split())
        graph[a - 1].append(b - 1)
        cnts[b - 1] += 1

    w = int(input()) - 1

    queue = deque()

    for i, c in enumerate(cnts):
        if c == 0:
            queue.append(i)

    memo = weights.copy()

    while queue:
        v = queue.popleft()

        for i in graph[v]:
            cnts[i] -= 1
            memo[i] = max(memo[i], memo[v] + weights[i])
            if cnts[i] == 0:
                queue.append(i)

        if cnts[w] == 0:
            print(memo[w])
            break