Connection Status:
Competition Arena > SkiResorts

SkiResorts

SRM 573 · 2012-12-13 · by rng_58

SRM 573 · 2012-12-13 · by rng_58 · Graph Theory
Class Name: SkiResorts
Return Type: long
Method Name: minCost
Arg Types: (vector<string>, vector<int>)
Problem Statement

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.

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
0)
{"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).

1)
{"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.

2)
{"NYN",
 "YNN",
 "NNN"}
{573, 573, 573}
Returns: -1

Place 2 is not reachable from place 0.

3)
{"NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN"}
{45480575, 12234374, 240534509, 824737523, 355275228, 877598227, 186741232, 89710658, 584173902, 740750698, 791578196, 327600804, 911659199, 25944107, 916994803, 556923148, 81086599, 649595391, 890286334, 734426951, 299512226, 191854377, 88299481, 543163019, 78322232, 430394496, 342410405, 299254411, 786861936, 89857845, 973940332, 975340024, 747476906, 17849462, 493628146, 691311309, 265702181, 41737032, 662899660, 524945548, 683229455, 445160588, 192924280, 365074349, 979257420, 977492448, 348055749, 992914905, 590769598, 530658547}
Returns: -1
4)
{"NNYNNYNNNYNNYNNNNNNNNNNNNNNNNYNNNNNNNYYNNNNNNNNNNN", "NNNNNNNNNNNYNNNNNNNNNNNYNNNNNNNNNNNNNNNNNNNNNNNNNN", "YNNNNYYNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNY", "NNNNNNNNNNNNNNNNYNNNNNNNNNNNNNNNNNNNNNNNNNNNNYNNNN", "NNNNNNNNNNYNNNNNNNNNNNNYNYNNNNNNNYNNNNNNNNYNNNNNNN", "YNYNNNNNNNNNYNNNNNNNNNNNNNNNNYNNNNNNNNNYNNNNYNNNNN", "NNYNNNNNNNNNNNNNNNNNNNNNNNNNNYNNNNNNNNYNNNYNNNNYNN", "NNNNNNNNNNNNNNNNYNNNNNNNNNNNNNNYNNNYNNNNNNNNNNNNNN", "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNYYNNYNNNNNYNNNNNNNNN", "YNNNNNNNNNNNNNNNNYNNNNNNNNNNNNNNNNNNNNNNYNNNNYNNNN", "NNNNYNNNNNNNNNNNNNNNYNNYNNNNNNYNNNNYNNNNNNNNNNNNNY", "NYNNNNNNNNNNNNNNYYNNYNNNNNNYNNNNNNNNNNNNNNNNNNYNNN", "YNNNNYNNNNNNNNNNNNNYNNNNNNYNNNNNYNNNNNNNNNNYNYNYNN", "NNNNNNNNNNNNNNNNNYYNNNNNNNNNNYNNNNYNNNNYNNNYYNNNNN", "NNNNNNNNNNNNNNNNNNNNNYNNYNNNYNNNNNYNNNNNNNNNNNNNNN", "NNNNNNNNNNNNNNNNNNNNNNNNNYNNYNNNNNNNNNNNNNNNNNNNNN", "NNNYNNNYNNNYNNNNNNNNNNNYNNNNNNYNNNNNNYNNNNNNNNNNNN", "NNNNNNNNNYNYNYNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", "NNNNNNNNNNNNNYNNNNNNNNNNNNYNNNYNNNNNYNNNNNNNNNNNNN", "NNNNNNNNNNNNYNNNNNNNNNNNYNNNNNNYNNNNNYNNNNNYNNNYNN", "NNNNNNNNNNYYNNNNNNNNNNYNNNNNNYNNYNNYNNNNNNNNNNNNNY", "NNNNNNNNNNNNNNYNNNNNNNNNNNYNNYNYNYNNNNNNNNNNNNNNNN", "NNNNNNNNNNNNNNNNNNNNYNNNNNNNNNNNNNYNYNNYNNNNYNNNNN", "NYNNYNNNNNYNNNNNYNNNNNNNNNNNNNNNNNYNNNNNNNNNYNNNNN", "NNNNNNNNNNNNNNYNNNNYNNNNNNNNNNNNNNNNNNNNNNNNYNNNNN", "NNNNYNNNNNNNNNNYNNNNNNNNNNNNNNNNNNNNNYNNNNNNNNNNNN", "NNNNNNNNNNNNYNNNNNYNNYNNNNNNNNNNNNNNNNNNNNNNYNNNNY", "NNNNNNNNNNNYNNNNNNNNNNNNNNNNNNNNNNNNNNNYNNNNNNNNNY", "NNNNNNNNNNNNNNYYNNNNNNNNNNNNNNNNNNNNNNNNYNNNNNNNNN", "YNNNNYYNNNNNNYNNNNNNYYNNNNNNNNNNNNNNNNNNNNNYNNNNNN", "NNNNNNNNYNYNNNNNYNYNNNNNNNNNNNNNNNNNNYNNNNYNNNNNNN", "NNNNNNNYYNNNNNNNNNNYNYNNNNNNNNNNNNNNNNNNNNNNNYNNNN", "NNNNNNNNNNNNYNNNNNNNYNNNNNNNNNNNNNNNNNNNNNNNNYNNNN", "NNNNYNNNNNNNNNNNNNNNNYNNNNNNNNNNNNNNNNNNNNNNNNNNYN", "NNNNNNNNYNNNNYYNNNNNNNYYNNNNNNNNNNNYNYYYNYNYNNNNNN", "NNNNNNNYNNYNNNNNNNNNYNNNNNNNNNNNNNYNNNNNNNNNNNNNNN", "NNNNNNNNNNNNNNNNNNYNNNYNNNNNNNNNNNNNNNNNNNNNNNNNYN", "YNNNNNNNNNNNNNNNYNNYNNNNNYNNNNYNNNYNNNNNNNNNNNYNNN", "YNNNNNYNNNNNNNNNNNNNNNNNNNNNNNNNNNYNNNNNNNNNYNNNNN", "NNNNNYNNNNNNNYNNNNNNNNYNNNNYNNNNNNYNNNNNYYNNNYNNYN", "NNNNNNNNYYNNNNNNNNNNNNNNNNNNYNNNNNNNNNNYNNNNNNNYNN", "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNYNNNNYNNNNYNNNNN", "NNNNYNYNNNNNNNNNNNNNNNNNNNNNNNYNNNNNNNNNNNNNNNNNNY", "NNNNNNNNNNNNYYNNNNNYNNNNNNNNNYNNNNYNNNNNNNNNYNNNNN", "NNNNNYNNNNNNNYNNNNNNNNYYYNYNNNNNNNNNNNYNNYNYNNNNNN", "NNNYNNNNNYNNYNNNNNNNNNNNNNNNNNNYYNNNNNNYNNNNNNNNNN", "NNNNNNNNNNNYNNNNNNNNNNNNNNNNNNNNNNNNNYNNNNNNNNNNNN", "NNNNNNYNNNNNYNNNNNNYNNNNNNNNNNNNNNNNNNNNYNNNNNNNNN", "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNYNNYNNYNNNNNNNNNN", "NNYNNNNNNNYNNNNNNNNNYNNNNNYYNNNNNNNNNNNNNNYNNNNNNN"}
{753715358, 540581625, 152449098, 160945771, 16828553, 170429425, 616662458, 677369677, 385699359, 834828376, 40886697, 406066324, 328626362, 167680674, 511647722, 772392466, 85032177, 752763520, 475571665, 958408612, 230986579, 935338015, 497660490, 552096442, 906884209, 544544068, 699091379, 933638925, 829031596, 97013135, 429659485, 742725345, 359048278, 125261550, 545269498, 939431690, 39756383, 542073115, 637145249, 398955324, 282710485, 379182718, 965338467, 436893857, 233350125, 45279687, 957967175, 51741708, 989243800, 83831358}
Returns: 0

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

Coding Area

Language: C++17 · define a public class SkiResorts with a public method long long minCost(vector<string> road, vector<int> altitude) · 147 test cases · 2 s / 256 MB per case

Submitting as anonymous