Drilling Head Control Unit
Deepest Drill Company, Ltd is producing a new set of drilling heads.
The drilling head control unit has a special durable design.
It consists of a ceramic base disk on which all electronics is mounted.
There are N slots situated on the perimeter of the base disk.
There are also N devices to be installed in the slots on the disk.
No slot can contain more than one device, but it is the advantage of the design
that any device can be installed in any slot.
The installed devices are subsequently connected into a single network which has a prescribed
tree topology. All connections between the devices must be laid on one side of the disk
and cannot cross each other.
Aside from that, the shapes and the lengths of the connections may be arbitrary.
The cost of installing a device in a slot depends on the particular slot and the particular device.
There is a cost matrix C which element C(i, j)
specifies the cost of installing the j-th device in the i-th slot.
The total installation cost is the sum of costs of installing all devices on the base disk.
It is desirable to assign the devices to the slots in such way that the total installation cost is minimized.
Image 1. An illustration of Example 1 below. a) The empty disk with 9 slots labeled 0, 1, ..., 8. b) The prescribed topology of the connections between the given 9 devices which are labeled 0, 1, ... 8. c) The optimal layout of the devices on the disk. The cost of installing a particular device in a particular slot is written in the speech bubble at the slot. All costs are specified in the cost matrix C given in Example 1. |
The task
You are given the installation cost matrix and the tree topology of the device connections. Find the minimum total installation cost.
Input
The first line of input contains one integer N describing the number of the
devices and number of the slots on the base disk. The slots and the devices are labeled by
integers 0,1, ..., N−1. The slots are situated on
the perimeter of the base disk in the order given by their labels.
The installation cost matrix C is specified on the next N lines.
Each of these lines represents one row of the matrix. The matrix entries are separated by
one or more spaces. Note that input lines may contain one or more leading spaces.
The value C(i, j) is a positive integer and it represents the cost of installing the
j-th device in the i-th slot.
Finally, the input contains N−1 lines which specify the connection topology.
Each of these lines contains the labels of two connected devices separated by space.
The order of connections and the order of devices on a line is arbitrary.
It holds 4 ≤ N ≤ 13, 1 ≤ C(i, j) ≤ 1000
for all 0 ≤ i, j < N.
Output
Ouput consists of one text line with one integer representing the minimum installation cost.
Example 1Input9 18 12 19 18 17 19 18 16 19 14 18 17 19 18 19 17 19 18 16 15 19 18 13 15 17 15 19 18 16 18 16 18 19 18 17 18 19 18 19 18 16 17 19 18 14 15 19 17 18 19 18 17 15 18 18 17 15 16 19 12 19 17 17 19 15 18 19 17 18 16 19 14 18 17 13 18 17 17 18 17 18 0 2 1 2 2 3 3 4 2 7 5 6 6 7 7 8Output 125 |
Image 2. The device installation resulting in minimum total installation cost in Example 1. |
Example 2Input4 70 90 10 80 20 70 80 90 80 30 90 70 90 80 70 40 0 2 0 3 1 2Output 180 |
Image 3. The device installation resulting in minimum total installation cost in Example 2. |
Example 3Input6 37 40 31 31 32 38 22 21 39 10 20 30 30 27 30 10 37 16 22 19 36 10 17 21 20 12 27 24 38 23 26 11 38 28 10 10 0 1 0 2 0 3 3 4 3 5Output 105 |
Image 4. The device installation resulting in minimum total installation cost in Example 3. |
Public data
The public data set is intended for easier debugging and approximate program correctness checking. The public data set is stored also in the upload system and each time a student submits a solution it is run on the public dataset and the program output to stdout and stderr is available to him/her.
Link to public data set