https://www.acmicpc.net/problem/30869
문제 요약
- N개 정류장(500개)
- 버스 : 시작, 끝, 소요시간, 주기
- K 번 빨리가기 : 주기와 상관 없이 바로 출발
- 가장 빨리 가는 시간은?
접근법
- 주기때문에 헷갈렸는데, 빨리가기가 없다면 빠른경로 => dijkstra
- 빨리가기를 사용한다면 => k 번 사용한 dijkstra
- 다만 처리를 안하면 메모리 초과가 발생함
- 모두 저장하면 500 * 500 노드에 대해서 작업해서 비효율이 있는 듯
- 아래 두개를 추가해줌
- 빨리가기를 안 써도 버스가 바로 출발하는 경우 처리 제외
- 빨리가기를 썼는데 안쓴 것보다 느려도 처리 제외
newbieski