레이팅 미적용2 \(s / 32\) \(MB / 100\) points
Little Mislav owns \(N\)
glasses of infinite volume, and each glass contains some water. Mislav
wants to drink all the water, but he doesn’t want to drink from more than \(K\)
glasses. What
Mislav can do with the glasses is pour the total volume of water from one glass to another.
Unfortunately, it matters to Mislav what glass he picks, because not all glasses are equally
distant to him. More precisely, the amount of effort it takes to pour water from glass labeled
with \(i\)
to glass labeled \(j\)
is denoted with \(C\)
ij.
.
Help Mislav and find the order of pouring the water from one glass to another such that the
sum of effort is minimal.
In test cases worth 40 points total, it will hold \(N\)
≤ 10.
The first line of input contains integers N, K
(\(1 \le K\) ≤ \(N\)
≤ 20).
The following \(N\)
lines contains \(N\)
integers \(C\)
\(ij\)
(0 ≤ \(C\)
\(ij\)
≤ 10 {5}{ }). The \(i\)
\(th\)
row and \(j\)
\(th\)
column contains
value \(C\)
\(ij\)
. It will hold that each \(C\)
\(ii\)
is equal to 0.
Output the minimal effort needed for Mislav to achieve his goal.
3 3
0 1 1
1 0 1
1 1 0
0
3 2
0 1 1
1 0 1
1 1 0
1
5 2
0 5 4 3 2
7 0 4 4 4
3 3 0 1 2
4 3 1 0 5
4 5 5 5 0
5