미로 탈출
시간 제한2초메모리 제한1024 MB
방이 N개 일렬로 놓인 미로에서 S번 방부터 E번 방까지 가장 빠르게 가는 경로 중 1번이나 N번 방으로 순간이동하는 횟수의 최솟값을 구합니다.
문제
주원이는 방 탈출을 하던 중 미로에 도착했다. 미로는 일렬로 놓인 개의 방으로 이루어져 있으며, 번 방과 번 방은 서로 인접해 있다 (). 각 방에는 스위치가 하나씩 있다. 주원이는 입구가 있는 번 방에서 출발해 모든 스위치를 누른 뒤, 출구가 있는 번 방으로 이동해 탈출해야 한다.
주원이가 쓸 수 있는 이동 방법은 두 가지다. 첫 번째는 비용 을 소모해 인접한 방으로 이동하는 것이다. 두 번째는 비용 을 소모해 번 또는 번 방으로 순간 이동하는 것이다. 두 이동 방법 모두 매번 1만큼의 시간이 걸린다. 스위치를 누르는 데는 시간이 들지 않는다.
방 탈출에서는 시간 관리가 중요하므로, 주원이는 미로를 가장 빠르게 빠져나가는 방법을 찾고자 한다. 가장 빠르게 탈출하는 방법들 가운데 비용이 최소인 방법을 찾아라.
입력
첫째 줄에 테스트 케이스의 개수 가 주어진다. 이어지는 각 줄에는 테스트 케이스마다 , , 가 공백으로 구분되어 주어진다.
출력
각 테스트 케이스에 대해 가능한 최소 비용을 한 줄에 출력한다.
제한
- 입력으로 주어지는 수는 모두 정수이다.