[Gold I] 횡단보도 - 24042

문제 링크

성능 요약

메모리: 325808 KB, 시간: 3616 ms

분류

그래프 이론, 최단 경로, 데이크스트라

제출 일자

2025년 11월 3일 12:30:15

문제 설명

당신은 집으로 가는 도중 복잡한 교차로를 만났다! 이 교차로에는 사람이 지나갈 수 있는 $N$ 개의 지역이 있고 그 지역 사이를 잇는 몇 개의 횡단보도가 있다. 모든 지역은 횡단보도를 통해 직, 간접적으로 연결되어 있다. 편의상 $N$ 개의 지역을 $1$부터 $N$까지로 번호를 붙이자.

당신은 이미 멀리서 교차로의 신호를 분석했기 때문에 횡단보도에 파란불이 들어오는 순서를 알고 있다. 횡단보도의 주기는 총 $M$ 분이며 $1$분마다 신호가 바뀐다. 각 주기의 $1+i(0\le i<M)$ 번째 신호는 $i,M+i,2M+i,3M+i,\cdots$ 분에 시작해서 $1$분 동안 $A_i$번 지역과 $B_i$번 지역을 잇는 횡단보도에 파란불이 들어오고, 다른 모든 횡단보도에는 빨간불이 들어온다. 한 주기 동안 같은 횡단보도에 파란불이 여러 번 들어올 수 있다.

횡단보도에 파란불이 들어오면 당신은 해당 횡단보도를 이용하여 반대편 지역으로 이동할 수 있으며 이동하는 데 $1$분이 걸린다. 횡단보도를 건너는 도중에 신호가 빨간불이 되면 안되기 때문에 신호가 $s\sim e$ 시간에 들어온다면 반드시 $s\sim e-1$ 시간에 횡단보도를 건너기 시작해야 한다.

횡단보도와 신호의 정보가 주어질 때, 시간 $0$분 에서 시작해서 $1$번 지역에서 $N$번 지역까지 가는 최소 시간을 구하는 프로그램을 작성하여라.

입력

첫 번째 줄에는 지역의 수 $N$, 횡단보도의 주기 $M$이 공백으로 구분되어 주어진다.

두 번째 줄부터 $M$ 개의 줄 중 $1+i$ 번째 줄에는 $i,M+i,2M+i,3M+i,\cdots$ 분에 시작해서 $1$분동안 파란불이 들어오는 횡단보도의 두 끝점 $A_i$, $B_i$가 공백으로 주어진다.

출력

첫 번째 줄에 $1$ 번 지역에서 $N$ 번 지역까지 가는데 필요한 최소 시간을 분단위로 출력한다.