SkiResorts | Topcoder Archive

Problem Statement

Fox Ciel is the owner of a ski resort. The ski resort has N places numbered 0 through N-1. There are some bidirectional roads between pairs of places. You are given a String[] roads. If the j-th character of the i-th element of roads is 'Y', there is a bidirectional road that connects place i and place j. If it is 'N', there's no road between them. You are also given a int[] altitude. The i-th element of altitude is the altitude of the place i.

You can go directly from the place i to the place j by skiing if there is a bidirectional road between them and the altitude of the place i is higher than or equal to the altitude of the place j. Ciel wants to reconstruct the ski resort so that place N-1 is reachable (not necessarily directly) from place 0 by skiing. In the reconstruction, Ciel can change the altitude of some places. The cost of changing the altitude of a place from x to y is |x - y| units of money, where || denotes the absolute value.

Return the minimal cost required for the reconstruction. If it is impossible to reach place N-1 from place 0 even after the reconstruction, return -1.

Definition

Class:: SkiResorts
Method:: minCost
Parameters:: String[], int[]
Returns:: long
Method signature:: long minCost(String[] road, int[] altitude)
(be sure your method is public)

Constraints

road will contain between 2 and 50 elements, inclusive.
Each element of road will contain exactly N characters, where N is the number of elements of road.
Each character in road will be either 'Y' or 'N'.
For each valid i, the i-th character of the i-th element of road will be 'N'.
For each valid pair (i, j), the i-th character of the j-th element of road and the j-th character of the i-th element of road will be equal.
altitude will contain exactly N elements.
Each element of altitude will be between 0 and 1,000,000,000, inclusive.

Examples

```
{"NYN",
 "YNY",
 "NYN"}
```
```
{30, 20, 10}
```
```
Returns: 0
```
It is possible to reach place 2 from place 0 even without the reconstruction by following the path (place 0) -> (place 1) -> (place 2).
```
{"NY",
 "YN"}
```
```
{10, 20}
```
```
Returns: 10
```
For example, Ciel can change the altitude of both places to 15. The cost is |10 - 15| + |20 - 15| = 10.

{"NYN",
 "YNN",
 "NNN"}

{573, 573, 573}

Returns: -1

Place 2 is not reachable from place 0.

{"NNYNNYYYNN",
 "NNNNYNYNNN",
 "YNNNNYYNNN",
 "NNNNNNYNYY",
 "NYNNNNNNYY",
 "YNYNNNNYNN",
 "YYYYNNNYNN",
 "YNNNNYYNNN",
 "NNNYYNNNNN",
 "NNNYYNNNNN"}

{7, 4, 13, 2, 8, 1, 8, 15, 5, 15}

Returns: 12

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.