패배한 전투는 언제나 군대를 약화하고 해체한다. 당면한 과제는 다시 집결하고, 그 집결 속에서 질서와 용기와 신뢰를 되찾는 것이다.
- 카를 폰 클라우제비츠, 『전쟁론』 제4편 제13장
문제를 열자마자 이런 소식을 전해서 미안하지만 당신은 막 중요한 전투에서 패배한 참이다. 당신이 지휘하던 부대들은 일부만이 살아남아 뿔뿔이 흩어져 스스로의 목숨을 구하기 위해 도망치고 있다.
당신의 목숨까지 패전의 대가로 치르고 싶지 않다면 패주하는 부대들을 수습하고 전열을 정비해서 전선이 무너지는 것을 막아야 한다.
적의 침투와 추가 진격을 막고 주요 통로와 거점을 유지하려면 패전으로 흩어진 부대들을 신속히 후방의 지정된 집결 지점으로, 예비대를 주요 방어 지점으로 이동시켜야 한다. 당신은 적에게 최대한 적은 기회를 허용하고 상황을 수습할 수 있도록 각 부대의 이동에 걸리는 시간을 최소화하려고 한다.
이 지역에는 이동의 출발지나 목적지가 될 수 있는 지점이 개 있으며 각 지점에는 번부터 번까지의 번호가 붙어 있다. 서로 다른 두 지점 사이에는 직접 이동할 수 있는 양방향 길이 있는데 번 지점에서 번 지점으로 직접 이동하는 데 걸리는 시간은 다음과 같다.
여기서 는 음이 아닌 정수이고 은 를 으로 나눈 나머지이다.
이동 중에는 다른 지점을 거쳐도 된다. 경로를 따라 이동하는 데 걸리는 시간은 경로에 포함된 각 길을 이동하는 데 걸리는 시간의 합이다.
당신은 부대를 재배치하기 위해 개의 이동 계획을 검토하려 한다. 각 계획에는 부대가 현재 있는 지점 와 목적지 가 주어진다. 각 계획에 대해 번 지점에서 번 지점까지 이동하는 데 걸리는 최소 시간을 구하여라.
첫째 줄에 정수 , , 가 공백으로 구분되어 주어진다.
다음 개의 줄에 각 이동 계획의 출발 지점과 목적지의 번호 , 가 공백으로 구분되어 주어진다.
각 이동 계획에 대해 최소 이동 시간을 주어진 순서대로 한 줄에 하나씩 출력한다.
예제 1의 첫 번째 계획에서는 번 지점에서 번 지점으로 직접 이동하면 만큼의 시간이 걸리며 이것이 최소이다.
예제 1의 두 번째 계획에서는 번 지점에서 번 지점으로 직접 이동하면 만큼의 시간이 걸리며 이것이 최소이다.
BCD 13 Ex번의 원본 형태이다.
이 문제를 풀었다면 BCD 13 Ex에도 도전해보자.
예제 2의 첫 번째 계획에서는 번 지점에서 번 지점으로 직접 이동하면 만큼의 시간이 걸린다. 의 경로로 이동하면 만큼의 시간이 걸리며 이것이 최소이다.
