Class Name: ShippingSequel
Method Name: addLegs
Parameters: Matrix2D
Returns: int
After losing nearly all its customers due to its dishonest ethics, Tom's
Shipping Company has decided to change its ways by offering non-stop routes
from warehouses to warehouses around the world.
Tom's Shipping Company is a marine shipping company. The company has W
warehouses on shores throughout the world. The warehouses are referred to by
number and are numbered 0 to W-1. Currently, the leg schedule consists of
regular direct trips (call them legs) from some warehouses to other warehouses.
Each leg has a length, in miles. The legs are directional; that is if there
is a leg of 100 miles from warehouse 0 to warehouse 1 there is not necessarily
a leg of 100 miles (or even a leg at all) from warehouse 1 to warehouse 0.
Tom's Shipping Company wants to create a new, expanded leg schedule by adding
more direct routes. The new schedule is based on the following rules (for all
combinations of A and B where A and B are non-negative integers less than the
number of warehouses and A and B are not equal):
*If there is currently a leg from warehouse A to warehouse B, the new schedule
will contain an identical leg from warehouse A to warehouse B.
*If there is currently some series of two or more legs, and no direct leg, to
get from warehouse A to warehouse B the new schedule will have a direct route
(1 leg) from A to B. The length of the added direct leg from warehouse A to B
is the same as the total length of the shortest (mileage wise) current series
of legs from warehouse A to B.
However, Tom's Shipping Company still wants to make a profit, so the total
additional mileage of the added routes must be as small as possible.
Implement a class ShippingSequel, which contains a method addLegs. The method
takes a Matrix2D as a parameter describing the current leg schedule. The
method returns an int that is the minimum possible total mileage of legs that
must be added to fulfill Tom's Shipping Company's goal of offering direct
routes where there used to be only indirect routes.
The current schedule is passed to the method as a Matrix2D. The Matrix2D (API
below) represents a 2-dimensional square matrix. The rows and columns are
numbered from 0 to W-1 (where W is the number of warehouses). The elements in
the matrix are referred to by ordered pairs of the form (row, column). The
element (0,0) is in the upper left of the matrix and the element (W-1,W-1) is
in the lower right the matrix. Each element (A,B) in the matrix is:
*-1 if there is currently no leg from warehouse A to warehouse B.
*The positive integer mileage of the leg from A to B if there is a leg from A
to B.
Note:
*Elements on the diagonal of the matrix (of the form (a,a)) represent legs from
warehouses to themselves. The mileage of these legs is always 0 in the current
and new schedule.
Here is the method signature:
public int addLegs(Matrix2D currentLegs);
currentLegs is a square matrix2D of Integers. The diagonal elements are 0.
Non-diagonal elements are -1 or positive Integers less than or equal to 1000.
currentLegs has minimum dimensions 1x1 and maximum dimensions 10x10.
Example:
If the company has 4 warehouses and the current leg schedule is:
*1 mile leg from warehouse 0 to warehouse 1
*6 mile leg from warehouse 0 to warehouse 2
*2 mile leg from warehouse 1 to warehouse 2
*4 mile leg from warehouse 2 to warehouse 3
Then, currentLegs =
0 1 6 -1
-1 0 2 -1
-1 -1 0 4
-1 -1 -1 0
There are indirect routes but no direct leg:
*From warehouse 0 to warehouse 3. The shortest route from 0 to 3 is 0->1->2->3
with length 1+2+4=7
*From warehouse 1 to warehouse 3. The shortest route from 1 to 3 is 1->2->3
with length 2+4=6
The new schedule is the old schedule plus:
*A leg from warehouse 0 to warehouse 3 of length 7
*A leg from warehouse 1 to warehouse 3 of length 6.
The new schedule has 7+6=13 added miles of legs, so the method returns 13.
See www.topcoder.com/api/index.html for Matrix2D api.