문제요약
- 정점, 간선, 가중치가 있는 그래프가 주어짐
- 시작은 1, 출구는 x개가 주어짐
- 출구가 열리는 시간이 규칙적이고 주기적임(문제에서 주어짐)
- 가장 빨리 탈출하는 시간 구하기
접근법
- 문제가 어려운 건 아닌데, 출구 시간 처리하는 부분이 좀 까다로움
- editorial 참고
- 일단 dijkstra로 시작점에서 모든 점 까지 최단 시간을 구해놓음
- 그리고 최단시간이 출구가 열리는 시간에 들어오는지를 판단함
- 출구는 k * x 주기로 반복이 되는 것을 이용함 : 주기를 P라고 하면
- 최단 시간을 P로 나눈 몫을 이용하거나 나머지를 구하면 최단 시간과 출구가 열리는 시간 사이의 관계를 구할 수 있음
- 시간 전이면 -> 출구가 열리는 시간에 나가면 됨
- 시간 후면 -> 다음번 열리는 시간에 나가면
- 출구 열리는 시간에 걸리면 -> 그 시간이 최단시간
실수했던 부분
- dijkstra를 구현할때 pair와 priority queue를 사용했는데, pq에 넣는 자료를 잘못 사용해서 오답 + 시간 초과 발생
- {거리, 노드} 로 pq에 넣어야하는데 {노드, 거리}로 넣었음
newbieski