싱그러운 날씨. 흔들리는 나뭇잎과 햇살. 다정한 인사와 안부. 마음이 담긴 메시지. 나를 감동하게 하는 것이나 내가 행복하다고 느끼는 순간을 적으라면 아마도 이 페이지를 빼곡하게 다 채울 수 있을 것 같다. 나는 감동과 행복의 역치가 낮은 사람.
- 바리수의《이젠 네가 피어날 차례야》중에서 -
* 저에게는 아주 작은 자극에도 감동과 행복을 느끼는 능력이 있습니다. 그래서인지 일상에서도 자주 감탄하고 감동하고 감사하고 행복해합니다. 내 감정마저 누군가의 허락을 받을 필요 없습니다. 나는 내 마음을 보냈고 그걸 받아주는 건 상대의 몫이니까요. 나는 그냥 내 몫의 일을 하면 되는 거니까요.
세상은 감사하는 자의 것이다. 내 인생에서 어떤 일이 일어나든 감사하는 법을 배웠을 때, 기회, 사람들과의 관계, 부까지도 내게로 다가왔다. 감사해야 할 것에 제대로 감사를 표하는 것, (역경, 고통, 슬픔 같은) 쉽게 감사하기 어려운 것에도 기꺼이 감사할 때, 인생은 분명 천국이 된다. - 오프라 윈프리
“행복은 감사하는 것이다. 감사는 더 많은 행복을 가져다준다. 부모에게 감사할 때 부모는 더 많은 것을 주려하고, 친구에게 감사할 때 그 친구는 더 많은 우정을 나누려 하며, 이웃에게 감사할 때 그 이웃은 더 많은 온정을 베풀려고 한다.” 쿠란에 나오는 감사예찬입니다.
건물 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])
