개발자 크루
남양연구소입니다.
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