세상은 감사하는 자의 것이다. 내 인생에서 어떤 일이 일어나든 감사하는 법을 배웠을 때, 기회, 사람들과의 관계, 부까지도 내게로 다가왔다. 감사해야 할 것에 제대로 감사를 표하는 것, (역경, 고통, 슬픔 같은) 쉽게 감사하기 어려운 것에도 기꺼이 감사할 때, 인생은 분명 천국이 된다. - 오프라 윈프리
“행복은 감사하는 것이다. 감사는 더 많은 행복을 가져다준다. 부모에게 감사할 때 부모는 더 많은 것을 주려하고, 친구에게 감사할 때 그 친구는 더 많은 우정을 나누려 하며, 이웃에게 감사할 때 그 이웃은 더 많은 온정을 베풀려고 한다.” 쿠란에 나오는 감사예찬입니다.
건물 W를 건설완료 하는데 드는 최소 시간을 출력한다. 편의상 건물을 짓는 명령을 내리는 데는 시간이 소요되지 않는다고 가정한다.
건설순서는 모든 건물이 건설 가능하도록 주어진다.
제한
2 ≤ N ≤ 1000
1 ≤ K ≤ 100,000
1 ≤ X, Y, W ≤ N
0 ≤ Di≤ 100,000, Di는 정수
>> 소스
import sys
from collections import deque
T = int(input(" 테스트 케이스 T 입력 : "))
for _ in range(T):
N,K=map(int,input(" 건물수, 건설 순서 : ").split())#건물수, 건설순서규칙
time=[0]+list(map(int,input(" 각 건물들의 건설시간 : ").split()))#건물들의 건설시간
seq=[[] for _ in range(N+1)]#건설순서규칙
inDegree=[0 for _ in range(N+1)]#진입차수
DP=[0 for _ in range(N+1)]#해당 건물까지 걸리는 시간
for _ in range(K):#건설순서규칙 저장
a,b=map(int,input(" 건설순서규칙 : ").split())
seq[a].append(b)
inDegree[b]+=1
q = deque()
for i in range(1,N+1):#진입차수 0인거 찾아서 큐에 넣기
if inDegree[i]==0:
q.append(i)
DP[i]=time[i]
while q:
a=q.popleft()
for i in seq[a]:
inDegree[i]-=1#진입차수 줄이고
DP[i]=max(DP[a]+time[i],DP[i])#DP를 이용해 건설비용 갱신
if inDegree[i]==0:
q.append(i)
ans = int(input(" W : "))
print(DP[ans])
