Class Name: ShippingTrilogy
Method Name: minMileage
Parameters: Matrix2D
Returns: int
Tom's Shipping Company is (once again) trying to cut costs and maximize profits.
Tom's Shipping Company is a marine based 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. In the current shipping schedule, there are
regular direct trips (call them legs) between certain pairs of warehouses. The
legs are bi-directional - if there is a leg from warehouse A to warehouse B,
there is an identical leg from warehouse B to warehouse A.
The company is developing a new shipping schedule such that the total combined
mileage of all its legs is as little as possible, yet the extent of the
schedule is not diminished. That is, if there is currently some series of 1 or
more legs to get from warehouse A to warehouse B, the new schedule must also
have a series of 1 or more legs to get from warehouse A to warehouse B.
Implement a class ShippingTrilogy which contains a method minMileage. The
method takes a Matrix2D as a parameter describing the current shipping
schedule. The method returns an int that is the sum of the mileages of the new
schedule in which the mileage is minimized while the extent of the schedule is
the same.
The Matrix2D (API: www.topcoder.com/api/index.html) parameter represents a
square two dimensional matrix with W rows and W columns. The elements in the
Matrix2D are referred to by ordered pairs of the form (row,col) where (0,0) is
in the upper left and (W-1,W-1) is in the lower right. Each element (A,B) in
the Matrix2D is:
*0 if there is currently no leg from warehouse A to warehouse B.
*A positive integer if there is currently a leg from warehouse A and B and the
integer is the mileage of the leg.
Because the legs are bi-directional, the Matrix2D is symmetrical: (A,B)=(B,A).
Elements along the diagonal (of the form (A,A)) are always 0 - There are no
legs from warehouses to themselves.
Here is the method signature:
public int minMileage(Matrix2D currentSchedule);
currentSchedule has the same number of rows as columns.
currentSchedule has dimensions between 1x1 and 20x20, inclusive.
Elements along the (A,A) diagonal are 0.
All other elements are non-negative integers less than 1000.
currentSchedule is symmetric - element (A,B) equal elements (B,A)
Examples:
If there are 6 warehouses, numbered 0 through 5, and the current schedule is:
[[0, 0, 3, 4, 0, 0]
[0, 0, 0, 0, 2, 1]
[3, 0, 0, 6, 0, 0]
[4, 0, 6, 0, 0, 0]
[0, 2, 0, 0, 0, 8]
[0, 1, 0, 0, 8, 0]]
There are routes between warehouses 0, 2, & 3 and between 1, 4, & 5.
The new schedule would contain the following legs:
Between 0 and 2: 3 miles
Between 0 and 3: 4 miles
Between 1 and 4: 2 miles
Between 1 and 5: 1 mile
because these legs have the minimum total mileage such that all routes in the
current schedule are also in the new schedule.
The method returns the total mileage of the new schedule: 10.