프로그램 명: ioi_trans
제한시간: 1 초

바이트랜드 왕국은 거의 모든 지역이 강과 숲으로 이루어져 있다. 상류의 작은 강들은 모여서 큰 강이 되며, 그 강도 다른 강과 만나 더 커져 나중에는 하류로 가면 거대한 강 하나만이 남아 바이트타운 근처의 바다로 흘러간다.

바이트랜드에는 나무꾼들이 사는 n개의 마을이 강변에 있다.

그런데 현재는 목공소가 강의 최하류인 바이트타운에 하나만 있기 때문에, 제각기 사는 곳에서 나무를 벤 나무꾼들은 통나무를 강에다 띄워서 그 목공소로 보낸다. 그래서 바이트랜드의 왕은 통나무를 하류로 흘려보내는 물류비용을 줄이기 위해, 마을들 중 적당한 곳에 k개의 목공소를 더 짓기로 했다.

목공소가 더 생기면, 상류에서 흘러보낸 통나무들은 바이트랜드까지 갈 필요 없이 처음으로 거치는 목공소에서 바로 처리를 할 수 있으며, 목공소가 있는 마을에서 생산된 통나무는 강을 거칠 필요조차 없어진다.

목공소를 세울 곳을 결정하기 위해, 왕의 신하들은 각 마을별로 연간 생산되는 통나무의 양을 조사해 두었다. 강물은 하류로 갈수록 합쳐지기만 하지 갈라지지는 않기 때문에, 각 마을에서 바이트타운까지 가는 경로는 오직 하나만 존재한다. 마을별로 강을 이용해 이웃 마을이나 현재의 최종 목적지인 바이트타운까지 가는 거리에 대한 자료 역시 있다. 이것을 토대로, 전국의 나무의 물류비용을 최소화하려면 어디에 목공소를 건설하면 좋을지 결정하는 프로그램을 작성하시오. 통나무 하나를 강으로 1km 거리만치 운반하는데 드는 비용은 1로 한다.

입력 형식

첫 줄에는 바이트타운을 제외한 마을의 수 n과 추가로 지으려고 하는 목공소의 수 k가 있다. (2≤n≤100, 1≤k≤50이고 k≤n) 마을들은 1부터 n까지 번호가 부여되어 있으며, 바이트타운의 번호는 0이다.

그리고 다음에는 n개의 줄이 더 있으며, i+1째 줄에는 각 마을에 대한 정보를 의미하는 세 개의 정수가 있다.

마을 전역에서 생산되는 통나무들을 바이트타운까지 운반하는데 드는 비용의 합은 20억을 넘어가지 않는다고 가정한다. 한편, 테스트 케이스들의 절반은 n의 값이 20을 넘지 않는다.

출력 형식

목공소를 최적의 위치에다 지었을 때, 마을 전역에서 생산되는 통나무를 "적당한 목공소가 있는 곳"까지 강으로 운반하는데 드는 최소 비용을 출력한다.

입출력 예 

입력

4 2
1 0 1
1 1 10
10 2 5
1 2 3

출력

4

위의 그림에서 선분은 강을 뜻하고, 원으로 된 정점은 마을을 뜻한다. 선분 위의 숫자는 해당 구간의 거리이며, 원 안의 숫자는 마을 번호, 그리고 원 아래의 숫자는 그 마을에서 매년 생산되는 통나무의 수이다.

이 예제에서 목공소를 지어야 하는 최적의 위치 두 곳은 2번과 3번 마을이다. 이 경우 4번 마을의 통나무를 2번 마을로 보내는 비용 1×3 과, 1번 마을의 통나무를 바이트타운으로 보내는 비용 1×1 만이 필요하다.

출처: ioi     
번역 http://moogi.new21.org/ioi17.htm#6:
[질/답] [제출 현황] [푼 후(2)]
[ 채 점 ] [홈으로]  [뒤 로]