시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 35 16 11 45.833%

문제

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

양항승 왕국에는 나무꾼들이 사는 n개의 마을이 강변에 있다. 그런데 현재는 목공소가 강의 최하류인 양항승 왕국에 하나만 있기 때문에, 제각기 사는 곳에서 나무를 벤 나무꾼들은 통나무를 강에다 띄워서 그 목공소로 보낸다. 그래서 항승이는  통나무를 하류로 흘려보내는 물류비용을 줄이기 위해, 마을들 중 적당한 곳에 k개의 목공소를 더 짓기로 했다. 목공소가 더 생기면, 상류에서 흘러보낸 통나무들은 왕국까지 갈 필요 없이 처음으로 거치는 목공소에서 바로 처리를 할 수 있으며, 목공소가 있는 마을에서 생산된 통나무는 강을 거칠 필요조차 없어진다.

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

입력

첫 줄에는 왕국을 제외한 마을의 수 n과 추가로 지으려고 하는 목공소의 수 k가 있다. (2≤n≤100, 1≤k≤50이고 k≤n) 마을들은 1부터 n까지 번호가 부여되어 있으며, 왕국의 번호는 0이다. 그 다음 각 n개의 각 줄마다 다음의 3개의 정수가 주어진다.

  • wi─마을 i에서 생산하는 나무의 개수
  • vi─마을 i에서 하류쪽으로 가면 나오는 첫번째 마을(혹은 왕국 본토)
  • di─마을 i에서 마을 vi까지의 거리

총 운반비는 2000000000을 넘지 않는다.

출력

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

예제 입력

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

예제 출력

4

힌트

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

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

출처

Olympiad > International Olympiad in Informatics > IOI 2005 6번