RUN
면접 대비시간 제한2초메모리 제한512 MB
N개의 감옥 방과 하나의 출구 E, 시간 제한 T가 주어질 때, T 시간 안에 E에 도달할 수 있는 방의 개수를 센다.
문제
사악한 범죄 조직이 수감자들을 감옥에서 탈출시키기로 했다. 감옥은 나선 모양으로 설계되어 있고 여러 개의 독방이 있다. 수감자들에게는 감옥을 빠져나갈 정해진 시간이 주어진다. 그 시간 안에 빠져나가면 석방되고, 그렇지 않으면 감옥 문이 다시 닫힌다. 감옥에는 나선 형태로 연결된 N개의 방이 있다. 각 방은 여러 다른 방과 통로로 이어져 있다. 감옥에는 E개의 출구 문이 있다. 탈출하는 동안 각 방에는 사람이 얼마든지 있을 수 있다.
수감자들이 모든 통로를 알고 있다고 가정할 때, 감옥을 빠져나갈 수 있는 수감자 수와 빠져나가지 못하는 수감자 수를 예측하는 프로그램을 작성하시오.
입력
입력의 처음 세 줄에는 다음이 주어진다.
- N: 감옥의 방 개수. 방은 1, 2, ..., N으로 번호가 매겨진다. (N <= 100)
- E: 출구 방의 번호. (0 < E < 100)
- T: 카운트다운 타이머의 시작값(임의의 시간 단위). (0 < T < 1000)
네 번째 줄에는 감옥의 연결 개수 M이 주어진다. 그다음 M개 줄에는 각각 방 사이의 연결(단방향 연결)을 나타내는 세 정수, 즉 두 방 번호 A와 B(1, ..., N 범위)와 A에서 B까지 이동하는 데 걸리는 시간 단위 수가 주어진다.
각 연결은 단방향이다. 즉, B에서 A로 가는 통로를 따로 지정하는 줄이 없으면 수감자는 B에서 A로 이동할 수 없다. 또한 방향에 따라 이동에 걸리는 시간이 다를 수 있다.
출력
출구 방에 도달한 수감자 수를 한 줄에 출력한다.