| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 (추가 시간 없음) | 1024 MB (추가 메모리 없음) | 1002 | 276 | 243 | 30.112% |
주원이는 방 탈출을 하던 중 미로에 도착했다. 미로는 일렬로 놓인 $N$개의 방으로 이루어져 있으며, $i$번 방과 $i+1$번 방은 서로 인접해 있다$(1\leq i<N)$. 또한, 각 방에 스위치가 하나씩 있어, 주원이는 입구가 있는 $S$번 방에서 출발하여 모든 스위치를 누르고, 출구가 있는 $E$번 방으로 이동하여 탈출해야 한다.
주원이는 두 가지 이동 방법을 사용할 수 있다. 첫 번째는 0ドル$ 만큼의 비용을 소모해 인접한 방으로 이동하는 것이고, 두 번째는 1ドル$ 만큼의 비용을 소모해 1ドル$번 또는 $N$번 방으로 순간 이동하는 것이다. 두 이동 방법 모두 매번 1 만큼의 시간이 소요된다. 스위치를 누르는 건 매번 0 만큼의 시간이 소요된다.
방 탈출에서 탈출하기 위해선 시간을 잘 관리해야 하므로 주원이는 최대한 빠르게 미로를 탈출하는 방법을 찾으려고 한다. 기록을 세우고 싶은 주원이를 위해서 가장 빠르게 미로를 탈출하는 방법 중 최소 비용으로 탈출하는 방법을 찾아주자.
첫째 줄에 테스트 케이스의 개수 $T$가 주어진다.
다음 줄부터 각 테스트 케이스마다 $N,ドル $S,ドル $E$이 한 줄에 공백으로 구분되어 주어진다.
각 테스트 케이스에 대해 가능한 최소 비용을 한 줄에 출력한다.
3 5 5 1 3 1 2 7 3 5
0 1 2
3번 테스트 케이스의 경우, 3ドル \rightarrow 4 \Rightarrow 1 \rightarrow 2 \Rightarrow 7 \rightarrow 6 \rightarrow 5$ 순서대로 이동해서 최단 시간일 때의 최소 비용으로 미로에서 탈출할 수 있다. 두 줄로 표시된 화살표가 순간이동을 쓴 시점이다.