import sys
input = sys.stdin.readline
from collections import deque
T = int(input())
for test in range(T):
N,K = map(int,input().split())
time = list(map(int,input().split()))
child = [[] for i in range(N+1)]
indegree = [0]*(N+1)
pretime = [0]*(N+1)
for i in range(K):
x1,x2 = map(int,input().split())
child[x1].append(x2)
indegree[x2] += 1
W = int(input())
dq = deque()
for i in range(1,N+1):
if indegree[i] == 0:
dq.append(i)
finish = False
while dq:
if finish:
break
x = dq.popleft()
for i in child[x]:
indegree[i] -= 1
pretime[i] = max(pretime[i],pretime[x]+time[x-1])
if indegree[i] == 0:
dq.append(i)
if i == W:
finish = True
break
print(pretime[W]+time[W-1])
위상정렬을 알기 전에 위상정렬로 풀어야되는지 모르고, BFS로 풀었다가, 다 익스트라 변형해서 풀었다가, 여러가지 방법을 며칠에 걸쳐서 시도해도 못풀었었던 문제이다.
위상정렬로 푸니까 바로 깔끔하게 정답이 나왔다.
기본적인 알고리즘은 위상정렬과 동일하고, 이때 추가로 pretime이라는 리스트를 만들어줘서 건물을 짓기 전에 걸린 시간들 중 최댓값을 저장하도록 하였다. 즉, 4번 건물을 짓기 위해서 2번, 3번 건물을 지어야 한다면, pretime[4]는 2번건물을 짓는데 걸린시간과 3번 건물을 짓는데 걸린시간 중 더 큰 값인 셈이다.
그리고 마지막에는 최종 건물을 짓는데 걸리는 시간을 더해서 출력한다.
오늘의 교훈) 뻘짓하지말자