밖의 평화와 안의 화합은 아름다운 것이다.
- 뤼벡의 옛 성문 비문
여러 도시가 상인들의 안전을 지키고 교역을 활성화하기 위해 무역 동맹을 맺었다. 당신은 동맹의 공동 기금을 관리하는 회계 담당자이다.
동맹은 회원 도시들 사이의 새로운 거래를 장려하려 한다. 이를 위해 서로 다른 두 회원 도시의 조합마다 첫 거래에서 물품 한 상자를 보내는 데 드는 운송비를 한 차례 지원하기로 했다.
동맹에 가입한 도시는 개이며 각 도시에는 번부터 번까지의 번호가 붙어 있다. 서로 다른 두 회원 도시 사이에는 직접 물품을 운송할 수 있는 양방향 교역로가 있다. 번 도시에서 번 도시로 물품 한 상자를 직접 운송하는 데 드는 비용은 다음과 같다.
첫째 줄에 정수 , 가 공백으로 구분되어 주어진다.
동맹이 준비해야 할 지원금의 총액을 출력한다.
예제 1에서 , , , , , 의 최소 운송비는 각각 , , , , , 이다. 따라서 필요한 지원금의 총액은 이다.
여기서 는 음이 아닌 정수이고 은 를 으로 나눈 나머지이다.
물품은 다른 회원 도시들을 거쳐 운송할 수도 있다. 한 상자의 운송비는 운송 경로에 포함된 각 교역로의 비용을 모두 더한 값이다. 상인들은 가장 적은 비용이 드는 경로를 선택한다. 각 거래의 운송비는 다른 거래와 독립적으로 계산한다.
운송 방향을 바꾸어도 최소 운송비는 같으며 동맹은 두 도시의 조합마다 한 번만 지원한다. 따라서 필요한 지원금의 총액은 인 모든 에 대해 번 도시에서 번 도시로 물품 한 상자를 운송하는 데 드는 최소 비용을 모두 더한 값이다. 동맹이 준비해야 할 지원금의 총액을 구하여라.
예제 2에서 , , 의 최소 운송비는 각각 , , 이다. 따라서 필요한 지원금의 총액은 이다.
