문제
런닝맨의 시청률이 떨어지고 있다고 느낀 제작진은 새로운 탈출게임을 개발하였다.
출연자는 미리 만들어진 트리모양의 길과 교차점을 이용하여 출발지로부터 목적지까지 가는 것이다.
게임을 좀 더 재미있게 하기 위하여 교차점을 통과할 경우에는 정해진 상금을 주거나 벌금을 내도록 하였다.
상금은 그 교차점에 도착하면 무조건 얻을 수 있지만 벌금이 있는 교차점은 출연자가 그 교차점의 벌금 이상으로 상금이 있는 경우 벌금을 내고 통과 할 수 있다.
교차점은 여러 번 방문할 수 있는데 한번 받은 상금과 낸 벌금은 다시 적용되지 않는다.
제작진은 여러 개의 맵을 만들었고 출연자가 선택할 수 있도록 하였다.
예를 들어 아래와 같은 맵이 있다고 하자.
원 안의 숫자는 교차점 번호 사각형 안의 숫자는 상금(양수) 또는 벌금(음수)이다.
시작점은 1, 도착점은 6이라고 할 경우 출발점 1에서 2로 이동하여 상금 2를 얻는다.
다시 3으로 이동하여 벌금을 지불한다.
4로 이동하여 상금 4를 획득한다.
왔던 길을 다시 돌아 교차점 2로 이동한 뒤 교차점 5로 가면서 벌금 3을 낸다.
도착점 6에 도착하므로 탈출에 성공할 수 있는 경우이다.
아주 재미있겠다고 생각한 제작진은 게임을 위한 맵을 만들었는데 맵이 복잡하다보니 만든 맵이 출발지로부터 목적지까지 도착할 수 있는지 정확히 알 수가 없었다.
고민하던 제작진은 천재적인 프로그래머인 당신에게 자문을 구해왔다. 당신의 실력을 발휘하여 떨어진 런닝맨의 시청률을 올리는데 기여해 보자.
입력
첫 행에 교차점의 수 N과 도착교차점 번호 E가 공백으로 구분되어 입력된다. ( 2 ≤ E ≤ N ≤ 200,000)
다음 행에 각 교차점의 상금(양수) 또는 벌금(음수)에 대한 정보 Ci가 공백으로 구분하여 주어진다. ( -1,000,000 ≤ Ci ≤ 1,000,000)
편의상 시작점은 1로 하며 시작점의 Ci는 음이 아니다. 이어서 N-1개의 길에 대한 정보가 행으로 구분하여 입력된다.
출력
입력된 정보에 대하여 탈출이 가능하다면 escaped, 불가능하다면 trapped를 행으로 구분하여 출력한다.
예제 #1
7 7
0 -3 2 2 3 -4 0
1 2
2 3
2 4
1 5
5 6
6 7
escaped
예제 #2
3 2
3 3 -4
1 3
2 3
trapped
로그인해야 코드를 작성할 수 있어요.