이번 문제는 위상정렬과 BFS, DP를 이용하여 해결하였다. 입력값을 저장할 때에 인접 리스트 형태로 저장해주고, 각 건물의 이전에 지어야 하는 건물의 갯수를 cnt리스트로 관리해주도록 하였다. 그리고 큐에 cnt가 0인 건물의 번호를 모두 담고, BFS를 통해 탐색을 하였다. 다음에 지어야 하는 건물을 순회하며 다음 건물에 대한 cnt리스트의 값을 1 감소시키고, 다음 건물에 대한 dp값을 최댓값으로 갱신하였다. 그리고 이 후, cnt리스트가 0이라면 큐에 다음 건물 번호를 담아 끝까지 건물을 탐색하도록 하였다. 이 함수가 끝나면 dp[w]를 출력하여 해결하였다.

Code

def bfs(q):
    while q:
        cur = q.popleft()
        for nxt in after[cur]:
            cnt[nxt] -= 1
            dp[nxt] = max(dp[cur]+d[nxt], dp[nxt])
            if not cnt[nxt]:
                q.append(nxt)
from collections import deque
t = int(input())
for _ in range(t):
    n, k = map(int, input().split())
    d = [0]+list(map(int, input().split()))
    after = [[] for _ in range(n+1)]
    cnt = [0 for _ in range(n+1)]
    for _ in range(k):
        a, b = map(int, input().split())
        after[a].append(b)
        cnt[b] += 1
    w = int(input())
    dp = [0 for _ in range(n+1)]
    q = deque()
    for i in range(1, n+1):
        if not cnt[i]:
            q.append(i)
            dp[i] = d[i]
    bfs(q)
    print(dp[w])