Police

TCCC07 Semi 3 · 2007-07-30 · by andrewzta

TCCC07 Semi 3 · 2007-07-30 · by andrewzta · Graph Theory, Greedy

Show categories

Class Name: Police

Return Type: int

Method Name: minimalCost

Arg Types: (vector<int>, vector<string>)

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.

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

{1, 2, 3, 4, 5}
{"NNNYY", "YNNNN", "NNNYN", "NNYNN", "NYNNN"}
Returns: 4

You can build police stations in cities 1 and 3.

{1000000,1000000}
{"NY", "YN"}
Returns: 1000000

It is enough to build one station.

{5, 3, 10, 4}
{"NYNN", "NNYN", "NNNY", "YNNN"}
Returns: 3

{6}
{"N"}
Returns: 6

{208, 901}
{"NN", "NN"}
Returns: 1109

Submissions are judged against all 70 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class Police with a public method int minimalCost(vector<int> cost, vector<string> roads) · 70 test cases · 2 s / 256 MB per case