TopCoder problem "Police" used in TCCC07 Semi 3 (Division I Level One)



Problem Statement

    

There are n junctions in the city, some of them are connected by one-way roads. The mayor of the city would like to build police stations at some junctions to fight crime in the city. Building a police station at junction i costs cost[i].

The police station at junction i is said to control junction j if it is possible for the police patrol to drive from junction i to junction j and back. Each junction must be controlled by some police station.

You are given int[] cost and String[] roads. The j-th character of the i-th element of roads is 'Y' if there is a one-way road from junction i to junction j, or 'N' of there is none. Return the minimal total cost to build the police stations.

 

Definition

    
Class:Police
Method:minimalCost
Parameters:int[], String[]
Returns:int
Method signature:int minimalCost(int[] cost, String[] roads)
(be sure your method is public)
    
 

Constraints

-cost will contain between 1 and 50 elements, inclusive.
-Each element of cost will be between 1 and 10^6, inclusive.
-roads will contain the same number of elements as cost.
-Each element of roads will contain n characters, where n is the number of elements of roads.
-Each element of roads will contain only characters 'Y' and 'N'.
-For all i the element i of roads[i] will be 'N'.
 

Examples

0)
    
{1, 2, 3, 4, 5}
{"NNNYY", "YNNNN", "NNNYN", "NNYNN", "NYNNN"}
Returns: 4
You can build police stations in cities 1 and 3.
1)
    
{1000000,1000000}
{"NY", "YN"}
Returns: 1000000
It is enough to build one station.
2)
    
{5, 3, 10, 4}
{"NYNN", "NNYN", "NNNY", "YNNN"}
Returns: 3

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=8253

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10958&pm=8253

Writer:

andrewzta

Testers:

PabloGilberto , vorthys , Olexiy , ivan_metelsky

Problem categories:

Graph Theory, Greedy