ReversingTheRoads | Topcoder Archive

Problem Statement

In some country every two distinct cities are connected by one-way road. You are the road architect and you wish that people of the country be able to travel between every possible pair of cities using the roads. To achieve your aim you can change directions of some roads to the opposite.

You will be given String[] cost. j-th character of i-th element of cost will be '-', if there is no road, which goes from city i to city j. Otherwise, j-th character of i-th element of cost will encode cost of reversing the direction of the road, which goes from city i to city j (characters 'a', 'b', ..., 'z' encode numbers 1, 2, ..., 26; characters 'A', 'B', ..., 'Z' encode numbers 27, 28, ..., 52). Return the minimum possible cost, which is needed to achieve your aim.

Definition

Class:: ReversingTheRoads
Method:: minimumCosts
Parameters:: String[]
Returns:: int
Method signature:: int minimumCosts(String[] cost)
(be sure your method is public)

Constraints

cost will contain between 3 and 50 elements, inclusive.
The number of characters in each element of cost will be the same as the number of elements in cost.
All characters in all elements of cost will be '-', 'a'..'z' or 'A'..'Z'.
i-th character in i-th element of cost will be '-'.
Exactly one of i-th character in j-th element of cost and j-th character in i-th element of cost will be '-'.

Examples

```
{"-a-",
 "--a",
 "a--"}
```
```
Returns: 0
```
Here we initially are able to travel between every pair of cities, so we don't need to reverse any roads.
```
{"-XZ",
 "--a",
 "---"}
```
```
Returns: 51
```
There are two variants: Reverse the road from city 0 to city 2 (cost 52). Reverse the roads from city 0 to city 1 and from city 1 to city 2 (cost 51). Second variant is better.
```
{"-A-Ya",
 "-----",
 "aZ-z-",
 "-a---",
 "-zaZ-"}
```
```
Returns: 26
```
Here it's enough to reverse just one road - from city 4 to city 1.

{"---------W",
 "U--M--Z-Xc",
 "YT-ZJvZAZY",
 "y-----G-BY",
 "Ow-S--Q-YP",
 "PX-Ww-Q-UQ",
 "C--------Y",
 "ID-QrfT-ZM",
 "X-----D--X",
 "----------"}

Returns: 49

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.