✍ 문제

문제링크: https://www.acmicpc.net/problem/1504

👏 풀이과정

이 문제는 위상정렬로 푸는 문제이다. 처음에 아 위상정렬로 풀면 되겠다 라고 생각했지만, 최대값을 구하는대에서 막혀 생각을 많이한 문제이다.
x -> y 라는 조건이 있을때 x건설 + y건설하는 시간이 저장되어 있는 y건설하는 시간보다 크면 바꾸어 주면 되는 dp문제이다. 점화식 dp[y] = max(dp[y], dp[x] + time[y])

import sys

T = int(sys.stdin.readline())

for _ in range(T):
    N, K = map(int,sys.stdin.readline().split())
    time = list(map(int,sys.stdin.readline().split()))
    array = [[] for _ in range(N+1)]
    input_deg = [0 for _ in range(N+1)]
    for _ in range(K):
        x, y = map(int,sys.stdin.readline().split())
        array[x].append(y)
        input_deg[y] += 1
    final = int(sys.stdin.readline())
    queue = []
    dp = [0 for _ in range(N+1)]
    for k in range(1 , N+1):
        if input_deg[k] == 0:
            queue.append(k)
            dp[k] = time[k-1]

    while queue:
        temp = queue.pop(0)
        for i in array[temp]:
            input_deg[i] -= 1
            dp[i] = max(dp[i], dp[temp] + time[i - 1])
            if input_deg[i] == 0:
                queue.append(i)

    print(dp[final])