https://www.acmicpc.net/problem/1005
1초 512MB
테크트리가 매 판마다 달라진다. 건물마다 짓는데 걸리는 시간이 다르고, 여러 건물을 동시에 짓기 시작할 수 있다. 특정 건물을 짓는데 걸리는 최소 시간을 출력하라.
첫째 줄에 TC 개수 T
각 TC별로
첫째 줄에 건물 개수 N과 건설 순서 규칙의 개수 K 건물 번호는 1번부터 N번까지 존재.
둘째 줄에 각 건물 건설에 걸리는 시간 D1~Dn
셋째줄 부터 K+2번째 줄까지 건설 순서 X Y ⇒ Y를 짓는데 X가 필요하다는 뜻
마지막 줄에는 지어야 할 건물 W
각 TC별로 목표 건물 짓는데 걸리는 가장 짧은 시간을 출력
안그래도 새로운 알고리즘 배워서 골아픈데 DP까지 응용해야됐어서 진짜 골 아팠던 문제
심지어 처음에는 DP 응용이 필요할지도 생각을 못했는데, 뭔가 구현이 난잡해진다 싶으면 어디선가 뭔가를 놓치지 않았나 생각해보자.