재우는 정올국에 배낭 여행을 왔다.

정올국은 N개의 도시로 이루어져 있고, 그 사이를 연결하는 기차 선로가 M개 있다.

각 기차 선로는 단방향이며, i번째 기차는 U_i번 도시에서 시작해서 V_i번 도시로 T_i분만에 이동한다.

재우는 기차 여행은 좋아하지만, 기차 환승은 그다지 좋아하지 않는다.

호구(?)와트로 가겠다고 킹크로스역에서 내려 플랫폼 9 3/4 벽에 냅다 부딪힌 경험이 있기 때문이다.

따라서 재우는 서로 다른 기차 선로는 최대 K개까지만 이용하려 한다.

또 재우는 철저히 계획적인 여행가이기 때문에, Q개의 여행 계획에 대해 미리 최적의 기차 노선을 알아보려 한다.

j번째 여행 계획은 시작 도시 C_j에서 D_j로 이동하는 것으로,

최적의 기차 노선은 주어진 조건을 만족하면서 이동 시간이 최소인 것이다.

만약 주어진 조건을 만족하면서 두 도시 사이를 이동할 수 없을 때에는, 계획을 파기한다.

재우가 여행 준비로 너무 바쁘다.

재우를 위하여 각 여행 계획에 대해 이동할 수 있는지 알아보고, 이동할 수 있다면 최적의 이동 시간을 구해주자.

이쯤 되면 재우는 분명 "쌤 저는 그럼 이문제 안풀어도 되나요?" 라고 할 것이다.

천만에 말씀 만만에 콩떡이다.

누군가 구해준다는 보장이 없을 뿐만 아니라

구해준 값이 맞는지 알 수 없기 때문이다. ^^

기차 여행 timer 1초 memory 1024MB

기차 여행 1초 1024MB