๋ฌธ์
https://www.acmicpc.net/problem/1005
๋ฐฑ์ค ๋ฌธ์ ์ง - 0x1A๊ฐ - ์์ ์ ๋ ฌ
์๊ณ ๋ฆฌ์ฆ: ๋ค์ด๋๋ฏน ํ๋ก๊ทธ๋๋ฐ, ๋ฐฉํฅ ๋น์ํ ๊ทธ๋ํ, ์์ ์ ๋ ฌ
ํ์ด

2056: ์์ ๋ฌธ์ ์ ๊ฐ์ ๋ก์ง์ด๋ค.
์์
์ด A → B ์์ผ๋ก ์ฒ๋ฆฌ๋๋ฏ๋ก B์ ํด๋น๋๋ ์์
๋ค์ ์ง์
์ฐจ์๋ฅผ ์ฆ๊ฐ์ํจ๋ค.
์ง์
์ฐจ์ ์ ๋ฆฌ๊ฐ ๋๋ฌ๋ค๋ฉด ์๋์ ๊ณผ์ ์ ๊ฑฐ์น๋ค.
- dp ๋ฆฌ์คํธ, queue ์์ฑ
- ์ง์
์ฐจ์๊ฐ 0์ธ ์์
๋ค์ ์ฐพ์
- dp๊ฐ์ ํด๋น ์์ ์ ์์์๊ฐ์ ์ ์ฅ
- queue์ ์ถ๊ฐ
- ์์์ ์ ์ฅํ queue๋ฅผ ๊ฐ์ง๊ณ BFS ์คํ
- queue: ์ง๊ธ ๋น์ฅ ์์ํ ์ ์๋ ์์ ๋ค
- queue์์ popํ ์์
๊ณผ ์ฐ๊ฒฐ๋ ์์
๋ค์ ํ์
- ์ฐ๊ฒฐ์์ ์ ์ง์ ์ฐจ์๋ฅผ 1 ๊ฐ์์ํด
- ์ฐ๊ฒฐ์์
์ dp๊ฐ์ ๊ฐฑ์ ํจ =>
max(๊ธฐ์กด dp๊ฐ, ํ์ฌ ์์ ์ dp๊ฐ + ์ฐ๊ฒฐ์์ ์ ์์์๊ฐ) - ์ง์ ์ฐจ์๊ฐ 0์ด ๋ ์ํ๋ผ๋ฉด queue์ ์ถ๊ฐ
- ๊ฑด์คํด์ผ ํ ๊ฑด๋ฌผ์ dp๊ฐ ์ถ๋ ฅ
์ ์ฒด ์ฝ๋
# 2056_์์
๊ณผ ๋น์ทํ ๋ฌธ์ . DP + BFS๋ฅผ ์ฌ์ฉํ๋ค.
# ๋ฉ๋ชจ๋ฆฌ: 37616KB / ์๊ฐ: 968ms
from sys import stdin
from collections import deque
input = stdin.readline
def bfs():
dp = [0] * (N+1)
queue = deque()
for i in range(1, N+1):
if in_degree[i] == 0:
queue.append(i)
dp[i] = time[i]
while queue:
curr = queue.popleft()
for node in graph[curr]:
in_degree[node] -= 1
# ํ์ฌ ๊ฑด๋ฌผ์ ์ง๋ ์ต์์๊ฐ = ๊ธฐ์กด๊ฐ or ์ด์ ๊ฑด๋ฌผ์ ์ง๋ ์ต์์๊ฐ + ํ์ฌ ๊ฑด๋ฌผ์ ์ง๋ ์๊ฐ
dp[node] = max(dp[node], dp[curr] + time[node])
if in_degree[node] == 0:
queue.append(node)
return dp[W] # W ๊ฑด๋ฌผ์ ์ง๋๋ฐ๊น์ง ์์๋๋ ์ต์ ์๊ฐ
T = int(input())
for _ in range(T):
N, K = map(int, input().split())
graph = [[] for _ in range(N+1)]
in_degree = [0] * (N+1)
time = [0] + list(map(int, input().split())) # ๊ฑด๋ฌผ์ ์ง๋๋ฐ ๊ฑธ๋ฆฌ๋ ์๊ฐ
for _ in range(K):
X, Y = map(int, input().split()) # X๋ฅผ ์ง์ด์ผ Y๋ฅผ ์ง์ ์ ์์
graph[X].append(Y)
in_degree[Y] += 1
W = int(input()) # ํ๊ฒ ๊ฑด๋ฌผ
print(bfs())