코딩 테스트/다이나믹 프로그래밍
[백준 1005번] ACM Craft 문제 풀이
서영선
2023. 9. 11. 10:55
< 문제 >
1005번: ACM Craft (acmicpc.net)
1005번: ACM Craft
첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N과 건물간의 건설순서 규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부
www.acmicpc.net
< 코드 >
from collections import deque
import sys
input = sys.stdin.readline
n = int(input())
for _ in range(n):
N, K = map(int, input().split())
arr = [[] for _ in range(N + 1)] # 연결된 건물 정보 배열
cnt_arr = [0] * (N+1)
time = [0] + list(map(int, input().split())) # 소요 시간 배열
for _ in range(K):
a, b = map(int, input().split())
arr[a].append(b)
cnt_arr[b] += 1
target = int(input())
dp = [-1] + [0]*N
q = deque()
for i in range(1, N+1):
if cnt_arr[i] == 0:
q.append(i)
dp[i] = time[i]
while q:
now = q.popleft()
for node in arr[now]:
cnt_arr[node] -= 1
dp[node] = max(dp[node], dp[now] + time[node])
if cnt_arr[node] ==0:
q.append(node)
if cnt_arr[target]==0:
print(dp[target])
break
