KBLTRNS
시간 제한2초메모리 제한512 MB
도착지에 도달하는 여러 경로가 각각 소요 시간과 가격을 가질 때, 12시간 제한 안에서 소요 시간이 가장 짧은 값을 출력한다.
문제
카불은 인구가 많은 도시다. 그러나 대중교통은 아직 충분히 발달하지 못했다. 그래서 아침과 저녁마다 사람들은 목적지까지 가는 데 많은 어려움을 겪는다. 이 도시의 좋은 점은 서로 다른 경로를 이용해 목적지에 도달할 수 있다는 것이다. 모든 경로에는 소요 시간과 요금이 정해져 있다.
어느 날 Toryalai는 급하게 처리해야 할 일이 생겼다. 그는 서둘러 가능한 한 빨리 목적지에 도착하려고 한다. Toryalai가 최소 시간에 목적지에 도달하도록 돕는 것이 당신의 일이다. Toryalai는 여러 경로를 이용해 목적지로 갈 수 있고, 경로는 여러 교차로로 이루어질 수 있다. 주어진 경로들 중에서 목적지까지 가는 최적의 경로를 찾아라.
참고: Toryalai는 경로를 바꿔 탈 수 없다.
입력
첫째 줄은 테스트 케이스의 수다. 둘째 줄(R)은 Toryalai가 목적지에 도달하는 데 사용할 수 있는 경로의 수다. 그다음 R개 줄에는 각 경로의 소요 시간과 요금이 주어진다. 시작점은 A이고 목적지는 D다. Toryalai가 가질 수 있는 최대 시간은 12시간이며, 각 경로 구간에 걸리는 시간은 분 단위로 주어진다.
참고:
최대 시간을 초과하는 경로는 없다.
모든 경로는 목적지에 도달한다.
출력
Toryalai가 소요 시간이 최소인 경로를 선택했을 때의 시간을 출력한다.