백준 - ACM Craft (1005)

위상 정렬로 풀 수 있다.

여기에 dp까지 추가했다.

indegree가 2개 이상인 노드를 생각해 보면

이미 값이 들어가 있는 경우 다시 한번 비교해 주어야 한다.

 

dp[k] = max(dp[k], dp[pop_data] + cost[k])

시작점에서 cost를 더한 것과 원래 목적지의 dp 값을 비교해서 높은 것으로 최신화

 

import heapq
def main():
    n = int(input())
    for _ in range(n):
        v ,e = map(int, input().split())
        cost = [0]+list(map(int, input().split()))
        graph = {i : [] for i in range(1,v+1)}
        indegree = [0]*(v+1)
        for _ in range(e):
            s, d = map(int,input().split())
            graph[s].append(d)
            indegree[d] += 1
        w = int(input())

        queue = []
        heapq.heapify(queue)
        dp = [0]*(v+1)
        for i in range(1,v+1):
            if indegree[i] == 0:
                heapq.heappush(queue, i)
                dp[i] = cost[i]

        while queue:
            pop_data = heapq.heappop(queue)
            for k in graph[pop_data]:
                indegree[k] -= 1
                dp[k] = max(dp[k], dp[pop_data] + cost[k])
                if indegree[k] == 0:
                    heapq.heappush(queue, k)
        print(dp[w])

main()