운하도시 풀스하임은 가운데에 큰 강이 자리잡은 무역도시로, 옛날부터 지리적 이점을 활용하여 운하를 통한 무역 활동을 꾸준히 하고 있다. 피아는 운하도시 풀스하임의 물자 수송 관리직을 맡아 도시의 발전에 큰 기여를 하고 있다.

최근 피아는 무역을 하는 배들이 강에 대한 정보가 없어 비효율적으로 움직인다는 것을 파악했다. 그래서 무역을 하는 배들이 빠르고 효율적으로 이동할 수 있도록, 출발과 도착 항구의 정보가 입력되면 제일 빠른 길을 알려주는 프로그램을 작성하였다. 하지만 강에 서식하는 거대한 용 때문에 배의 이동시간이 바뀌는 일이 다반사였고, 피아의 프로그램은 이런 상황에서 매우 느렸다. 결국 피아는 알고리즘을 매우 잘 아는 여러분에게 도움을 요청했다.

구체적으로 운하도시 풀스하임에서 항구는 그림과 같이 강 위쪽에 n개, 아래쪽에 n개가 나란히 위치해 있다. 또한, 강이 혼잡해지지 않도록 배는 그림에서 인접한 항구끼리만 이동할 수 있다.

항구와 뱃길에는 번호가 붙어있다. 왼쪽 위 항구가 1번, 왼쪽 아래가 n+1번이고, 오른쪽으로 가면서 순서대로 번호가 붙는다. 뱃길도 왼쪽 위 뱃길이 1번, 왼쪽 가운데 뱃길이 n번, 왼쪽 아래 뱃길이 2n번이고, 오른쪽으로 가면서 순서대로 번호가 붙는다. 그림에서 n=7인 경우의 예시를 확인할 수 있다.

피아는 구체적으로 다음과 같은 쿼리를 수행할 수 있는 프로그램을 원한다.

1. 특정 뱃길의 소요 시간이 바뀐다.
2. 주어진 두 항구 사이를 이동하는 데 소요되는 최단시간을 출력한다.

피아를 도와 프로그램을 작성해주자!

#3596 upload 4 done 1 how_to_reg 1

운하도시 timer 3s memory 1024MB

#3596

운하도시 3s 1024MB