INPUT FILE: time.in
OUTPUT FILE: time.out
Consider the problem of sending a packet of information (a warning, say) through a network: the packet originates at some computer and propagates through the network, splitting at every possible junction. The latter is done to ensure that the package will get to every computer. Given the delays, i.e. length of time for the packet to travel through each section of the wire how long will it take before every computer in the network (every node) obtains the packet?
INPUT
The first line contains the number of nodes 0 < N <= 100 in the network.
The next N lines contain a symmetrical matrix giving the direct connection times
between each pair of computers. Negative values indicate computers that are
not directly connected.
The last line contains a number between 1 and N inclusive indicating the computer
at which the packet originated.
OUTPUT
Output the time for information to spread to every computer or "Infinity"
if propagation is not possible.
Sample Input File
3 1 1 10 1 1 2 10 2 1 1 3 1 2 -1 2 1 -1 -1 -1 1 2
Output for Sample Input (Other answers are possible)
3 Infinity