미로 탈출

시간 제한2초메모리 제한1024 MB

요약
일렬로 놓인 N개의 방에서 S에서 출발해 모든 스위치를 누르고 E로 탈출할 때, 인접 이동은 무료이고 1번 또는 N번 방으로의 순간 이동에 드는 최소 비용을 구한다.
난이도

보통10점 중 4점

유형
그리디, 수학, 구현, 배열
정답자
아직 제출이 없습니다

문제

주원이는 방 탈출을 하던 중 미로에 도착했다. 미로는 일렬로 놓인 NN개의 방으로 이루어져 있으며, ii번 방과 i+1i+1번 방은 서로 인접해 있다(1≤i\<N)(1\leq i\<N). 또한, 각 방에 스위치가 하나씩 있어, 주원이는 입구가 있는 SS번 방에서 출발하여 모든 스위치를 누르고, 출구가 있는 EE번 방으로 이동하여 탈출해야 한다.

주원이는 두 가지 이동 방법을 사용할 수 있다. 첫 번째는 00 만큼의 비용을 소모해 인접한 방으로 이동하는 것이고, 두 번째는 11 만큼의 비용을 소모해 11번 또는 NN번 방으로 순간 이동하는 것이다. 두 이동 방법 모두 매번 1 만큼의 시간이 소요된다. 스위치를 누르는 건 매번 0 만큼의 시간이 소요된다.

방 탈출에서 탈출하기 위해선 시간을 잘 관리해야 하므로 주원이는 최대한 빠르게 미로를 탈출하는 방법을 찾으려고 한다. 기록을 세우고 싶은 주원이를 위해서 가장 빠르게 미로를 탈출하는 방법 중 최소 비용으로 탈출하는 방법을 찾아주자.

입력

첫째 줄에 테스트 케이스의 개수 TT가 주어진다.

다음 줄부터 각 테스트 케이스마다 NN, SS, EE이 한 줄에 공백으로 구분되어 주어진다.

출력

각 테스트 케이스에 대해 가능한 최소 비용을 한 줄에 출력한다.

제한

  • 1≤T≤1041\leq T\leq 10^4
  • 2≤N≤1092\leq N\leq 10^9
  • 1≤S,E≤N1\leq S,E\leq N
  • S≠ES\neq E
  • 입력으로 주어지는 수는 모두 정수이다.

예제1

  1. 예제 1

    입력
    3
    5 5 1
    3 1 2
    7 3 5
    
    예상 출력
    0
    1
    2