Class Name: Barricades
Method Name: minBarricadeWidth
Parameters: int,String[]
Returns: int
Police have been warned that three million dollars of illegal drugs are being
moved from drug dealer Ed's warehouse to drug dealer Joe's warehouse. A
network of two way roads connect Ed's warehouse to Joe's warehouse and the
police are going to barricade some of the roads so the truck carrying the drugs
cannot get to Joe's. Each road has a fixed width and the police want the sum
of the widths of the barricades across all roads to be as small as possible.
Implement a class Barricades that contains a method minBarricadeWidth. The
method takes an int and a String[] describing the road network and returns an
int that is the minimal total barricade width such that there is no
barricadeless series of roads from Ed's to Joe's.
The int input, N, is the number of nodes in the road network between Ed's and
Joe's. The nodes are numbered from 0 to N-1. Node 0 is Ed's warehouse and
node N-1 is Joe's house. Each String[] element describes a road connecting two
nodes. The String[] elements are of the form (quotes for clarity) "N1 N2 W"
where N1 and N2 are the two nodes the road connects and W is the width of the
road (which equals the length of a barricade across the road, if a barricade is
put across the road). The roads are two way.
Here is the method signature:
public int minBarricadeWidth(int N,String[] roads);
N is between 2 and 10, inclusive.
roads has at most 15 elements.
Each element is of the form "N1 N2 W" where N1 and N2 are non-negative integers
less than N and W is a positive integer less than 100.
No two elements refer to the same two nodes. That is both "3 1 2" and "1 3 4"
cannot be in the String[].
There are no roads from a node to itself.
TopCoder will check the validity of the input.
Note:
*If there is no way to get from Ed's to Joe's, police do not have to barricade
any road and the method returns 0.
Example:
*If there are N=5 nodes and the roads are given in the ArrayList are:
roads={"0 1 5","0 2 2","0 3 3","1 2 1","2 3 1","2 4 10","3 4 2"}
Then barricading the roads between 0 & 2 (width 2), 1 & 2 (width 1), 2 & 3
(width 1), and 3 & 4 (width 2) results in the smallest possible width of
barricades such that there is no barricadeless route from node 0 to node 4 and
the method returns the minimal width = 2+1+1+2 = 6.
|