Task: RIV
Rivers
Monday, 22–08–2005
Available memory: 32 MB. Maximum running time: 1 s.
Nearly all of the Kingdom of Byteland is covered by forests and rivers. Small rivers meet to form bigger
rivers, which also meet and, in the end, all the rivers flow together into one big river. The big river meets the
sea near Bytetown.
There are n lumberjacks’ villages in Byteland, each placed near a river. Currently, there is a big sawmill
in Bytetown that processes all trees cut in the Kingdom. The trees float from the villages down the rivers to
the sawmill in Bytetown. The king of Byteland decided to build k additional sawmills in villages to reduce
the cost of transporting the trees downriver. After building the sawmills, the trees need not float to Bytetown,
but can be processed in the first sawmill they encounter downriver. Obviously, the trees cut near a village
with a sawmill need not be transported by river. It should be noted that the rivers in Byteland do not fork.
Therefore, for each village, there is a unique way downriver from the village to Bytetown.
The king’s accountants calculated how many trees are cut by each village per year. You must decide
where to build the sawmills to minimize the total cost of transporting the trees per year. River transportation
costs one cent per kilometre, per tree.
Task
Write a program that:
• reads from the standard input the number of villages, the number of additional sawmills to be built, the
number of trees cut near each village, and descriptions of the rivers,
• calculates the minimal cost of river transportation after building additional sawmills,
• writes the result to the standard output.

Example

For the input data:
4 2
1 0 1
1 1 10
10 2 5
1 2 3
the correct result is:
4
5
10
1
3
0
2
4
3
1
Bytetown
1
1
1
10
The above picture illustrates the example input data. Village numbers are given inside circles. Numbers
below the circles represents the number of trees cut near villages. Numbers above the arrows represent
rivers’ lengths.
The sawmills should be built in villages 2 and 3.
v. 1.04
2/2
Rivers

Note (RiseOJ) — The original statement describes file-based input/output; on this judge your program must read from standard input and write to standard output instead.

The first line of input contains two integers: n — the number of villages other than Bytetown (2 ≤n ≤100),
and k — the number of additional sawmills to be built (1 ≤k ≤50 and k ≤n). The villages are numbered
1,2,...,n, while Bytetown has number 0.
Each of the following n lines contains three integers, separated by single spaces. Line i+1 contains:
• wi — the number of trees cut near village i per year (0 ≤wi ≤10000),
• vi — the first village (or Bytetown) downriver from village i (0 ≤vi ≤n),
• di — the distance (in kilometres) by river from village i to vi (1 ≤di ≤10000).
It is guaranteed that the total cost of floating all the trees to the sawmill in Bytetown in one year does not
exceed 2000000000 cents.
In 50 % of test cases n will not exceed 20.
v. 1.04
½
Rivers

The first and only line of the output should contain one integer: the minimal cost of river transportation (in
cents).

생성자가 기록되지 않았습니다.

출처 IOI 2005