# 1005 ACM Craft

문제 : <https://www.acmicpc.net/problem/1005>

```python
import sys
input=sys.stdin.readline
from collections import deque
import heapq

# 다 지었으면 다음 건물 indegree 지워주고 
# 다음 건물을 지을까말까 확인하는 과정
def next_building(B,build_order,indegree,sub_Q):
    for next in build_order[B]:
        indegree[next]-=1
        if indegree[next] == 0:
            sub_Q.append(next)

T=int(input())
for _ in range(T):
    # 각 경기에 대한 정보 받아오기
    total_time=0
    N,K=map(int,input().split()) # N: 건물개수, K: 건물순서규칙개수
    build_time=[0]+list(map(int,input().split()))
    build_order={i:[] for i in range(N+1)}
    indegree=[0 for _ in range(N+1)]
    for _ in range(K):
        X,Y=map(int,input().split())
        build_order[X].append(Y) # X를 지은 후에 Y를 지을 수 있음
        indegree[Y]+=1
    win=int(input())

    # 처음 지을 건물들 우선순위 큐에 넣기
    now_building=[]
    for i in range(1,N+1):
        if indegree[i]==0:
            heapq.heappush(now_building,[build_time[i],i])
    # 짓기 시작
    while now_building:
        sub_Q=deque()
        build = heapq.heappop(now_building)
        B_t, B = build[0], build[1]
        total_time += B_t
        if B == win:
            break
        if B_t == 0:
            continue
        Qsize = len(now_building)
        next_building(B,build_order,indegree,sub_Q)
        # 다른 건물들도 동시에 지을 수 있기 때문에 고려
        for i in range(Qsize):
            now_building[i][0] -= B_t
            if now_building[i][0]==0:
                next_building(now_building[i][1],build_order,indegree,sub_Q)
        # 순서가 섞이니까 유예를 둔 뒤에 추가하기
        for b in sub_Q:
            heapq.heappush(now_building,[build_time[b],b])
    print(total_time)
                
# now_building[i][0] 부분에 build 써버림
# win을 만들면 종료되게 하는거 깜빡함 - 결과가 말해주니까 알았지만
# heappush로 들어가버리면 이전에 짓고 있던 건물들과 섞여버림
```

위상 정렬이 체화되지 않아 까먹었던 상태라

bfs로 어떻게든 맞았습니다 띄웠지만

```python
import sys

sys.setrecursionlimit(1000000)

def ACMcraft(n):
    if not graph[n]:
        return time[n]
    
    if dp[n] == -1:
    
        for bef in graph[n]:
            dp[n] = max(dp[n], ACMcraft(bef) + time[n])
    
    return dp[n]

input = sys.stdin.readline

T = int(input())
for _ in range(T):#재귀dp돌릴거임
    N, K = map(int, input().split())
    time = [-1] + list(map(int, input().split()))
    dp = [-1] * (N+1)
    graph = [[] for _ in range(N+1)] #선행과정 가리킴

    for _ in range(K):
        x, y = map(int, input().split())
        graph[y].append(x)
    W = int(input())

    print(ACMcraft(W))
```

<https://www.acmicpc.net/source/83904073>

dp 역탐색 재귀로 풀면 복잡하게 수식 죽 쓸 필요도 없다.


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://lazyartisan.gitbook.io/note/main-page/algorithm/undefined-1/1005-acm-craft.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.