A campus network is constituted by n computers, which are mutually connected
by net line,as the picture shows.The vertexs represent computers, the edges
represent net lines.As you see, different net lines have different transmission
capacities, for example, it will take 32 sec to transmit information from
Computer 1 to Computer 2, while 10 sec from 2 to3, and at least 44 sec
from 1 to 5(through v3).Now we know that the school has bought m accelerating
devices, each of which can halve the transmitting time of a net line. One net
line can afford multiple devices, that is to say,when 2 devices are connected
to one line, the time will be shorten to 1/4 of the original one, thus 1/8
when 3 devices are used. It remains an urgent problem that how to distribute
those devices approprately to make the time shortest from 1 to n.The school
officials employ you to solve this problem.As the it shows, if m=2, that is
to say ,two devices are used for Line 1-3 and Line 3-5, then the time will
be 22 sec.
Input as follows.The first row has integer n and m(1 < n <= 100,0 <= m <= 10).
The following n rows, each row has n real numbers.Row i and Column j mean the
Computer i and Computer j are connected.0 means no line between the computers.
(fabs() is recommended)
Output the shortest time from 1 to n by m devices.Printed exact to two digits
to the right of the decimal point.
0 34 24 0 0
34 0 10 12 0
24 10 0 16 20
0 12 16 0 30
0 0 20 30 0