개발자 크루

[RecurDyn]

취미로 코딩하는 RecurDyn 개발자 모임

Lv.4

썸네일

[한양대 HCPC 2023] 빨리 기다리기

난이도
4 단계
참가자
0 명
제출
0 명
정답률
0.00 %
언어별 시간/메모리
언어별 시간/메모리 표
언어 시간 메모리
C++ 2초 1024MB
JavaScript 8초 1024MB
C 2초 1024MB
Java 6초 1024MB
Python 8초 1024MB

재원이의 마을에는 N개의 버스 정류장과 M개의 버스 노선이 있다.


 i번 노선은 si번 정류장에서 출발해 ti시간 후 ei번 정류장에 도착하며, si번 정류장과 ei번 정류장을 제외한 다른 정류장에는 멈추지 않는다. 또한, 배차 간격 gi가 있어 0시에 si번 정류장에서 버스가 운행을 시작한 뒤, 매 gi시간마다 si번 정류장에서 버스가 운행을 시작한다.


빨리 도착해야 하는 재원이는, 빨리 기다리기를 사용하기로 했다. 빨리 기다리기를 사용하면, 현재 정류장에서 출발하는 노선 중 하나를 선택해 배차 간격과 무관하게 지금 당장 출발하도록 할 수 있다.


빨리 기다리기를 최대 K번 사용해 1번 정류장에서 N번 정류장까지 가는 데에 걸리는 최소 시간을 재원이에게 알려주자.

제약조건

2 ≤ N ≤ 500

1 ≤ M ≤ 250,000

0 ≤ K ≤ 500

1 ≤ si,ei ≤ N

si ≠ ei

1 ≤ ti ≤ 10,000

1 ≤ gi ≤ 10,000

입력형식

첫 번째 줄에 정류장의 개수 N, 노선의 개수 M, 빨리 기다리기를 사용할 수 있는 최대 횟수 K가 공백으로 구분되어 주어진다.

 M개의 줄에 걸쳐 버스 노선의 정보가 주어진다. i+1번째 줄에는 i번 버스 노선의 정보 si, ei, ti, gi가 공백으로 구분되어 주어진다.

출력형식

첫 번째 줄에 1번 정류장에서 N번 정류장까지 가는 데에 걸리는 최소 시간을 출력한다. 불가능한 경우에는 −1을 출력한다.

입력예제1

3 3 1
1 3 7 2
1 2 2 5
2 3 4 4
출력예제1

6
입력예제2

5 8 500
1 2 9998 1
2 4 4 1
1 3 9997 1
3 4 6 1
4 1 10000 1
4 2 10000 1
4 3 10000 1
4 5 10000 1
출력예제2

20002