Problem Statement |
| | There's a far away country where only builders live. They have built a number of cities already, and some of them are connected with bidirectional roads. The existing roads are given in the String[] g, where the j-th character of the i-th element is 'Y' if there's a bidirectional road connecting cities i and j, and 'N' otherwise. Each city contains a number of houses, given in the int[] before, where the i-th element is the number of houses in city i. Exactly one builder lives in each house.
The country will go through a two-phase building process. In the first phase, new bidirectional roads will be built so that every pair of cities will be connected by some path. When a road is built between two cities, every builder from both cities will be involved and each builder will be paid roadCost units of money.
In the second phase, new houses will be built. You are given a int[] after, where the i-th element is the number of houses that must exist in city i after this phase is complete. In other words, after[i] - before[i] new houses must be built in city i during this phase. When a house is built, all builders in that city and all its neighboring cities will be involved and each one will be paid houseCost[i] units of money. Two cities are neighboring if they are directly connected by a road. After each house is built, a new builder will immediately live in that house. Houses can be built in any order.
Return the minimal possible cost required to finish both phases of the building process. |
| |
Definition |
| | | Class: | BuildersCountry | | Method: | minCost | | Parameters: | int[], int[], int[], String[], int | | Returns: | long | | Method signature: | long minCost(int[] before, int[] after, int[] houseCost, String[] g, int roadCost) | | (be sure your method is public) |
|
| |
|
| |
Constraints |
| - | before will contain between 1 and 50 elements, inclusive. |
| - | Each element of before will be between 1 and 100000, inclusive. |
| - | after will contain the same number of elements as before. |
| - | The i-th element of after will be between the i-th element of before and 100000, inclusive. |
| - | houseCost will contain the same number of elements as before. |
| - | Each element of houseCost will be between 1 and 100000, inclusive. |
| - | g will contain the same number of elements as before. |
| - | Each element of g will contain exactly n characters, where n is the number of elements in g. |
| - | Each element of g will contain only uppercase letters 'Y' and 'N'. |
| - | The i-th character of the i-th element of g will always be 'N'. |
| - | The i-th character of the j-th element of g will always be equal to the j-th character of the i-th element of g. |
| - | roadCost will be between 1 and 100000, inclusive. |
| |
Examples |
| 0) | |
| | {2, 1, 3, 5} | {2, 1, 3, 5} | {4, 5, 3, 2} | {"NNNN", "NNNN", "NNNN", "NNNN"} | 1000 |
| Returns: 13000 | | We can build roads from city 1 to all other cities for a total cost (1+2)*1000 + (1+3)*1000 + (1+5)*1000 = 13000. All houses are already built. |
|
|
| 1) | |
| | {1, 1, 1, 1} | {1, 3, 1, 2} | {8, 5, 3, 2} | {"NYNN", "YNYN", "NYNY", "NNYN"} | 100000 |
| Returns: 39 | | We don't need to add any roads. If we build one house in city 1, we need to pay 5*(1+1+1). After that, build one house in city 3 for a cost of 2*(1+1). Then, build another house in city 1. This time, the cost will be 5*(1+2+1) since 2 workers now live in city 1. The total cost is 15+4+20=39. |
|
|
| 2) | |
| | {9, 11} | {10, 11} | {5, 1} | {"NN", "NN"} | 15 |
| Returns: 400 | | Build one road and build one house. |
|
|
| 3) | |
| | | Returns: 999000 | | Build 999 houses. Total cost is (1+2+...+999)*2 = 999000. |
|
|
| 4) | |
| | {99, 23, 44, 55, 32} | {99, 23, 44, 55, 32} | {39, 32, 11, 23, 89} | {"NYNNN", "YNNNY", "NNNYY", "NNYNY", "NYYYN"} | 54 |
| Returns: 0 | |
|