Problem Statement |
| | Little Johnny has just been named minister of transportation for the republic of Feudalia. Feudalia currently lacks any means of transportation between its cities, which has prompted Little Johnny to begin the planning process for a new transportation network for the twentieth century. To do so, Feudalia may build roads to connect pairs of cities and may also build airports within cities. Each airport costs airportCost to build. The construction of a road of length L will cost roadCost x L. A road must be a straight line between two cities. Although roads may cross, road travel between two cities must be done in a straight line. Air travel is possible between two cities if and only if both cities have an airport. Little Johnny requires every city in Feudalia to be reachable from all the other cities. Formally, a city B is reachable from a city A if any of the following conditions is true:
- There is a straight line road between A and B.
- Both A and B contain airports.
- There exists some city C, such that B is reachable from C and C is reachable A.
You are given the coordinates of the cities as two int[] cityX and cityY such the i-th city will have cartesian coordinates (cityX[i], cityY[i]). You are also given roadCost and airportCost. Return the minimum cost the ministry of transportation will have to incur. |
| |
Definition |
| | | Class: | TransportationNetwork | | Method: | minCost | | Parameters: | int[], int[], double, double | | Returns: | double | | Method signature: | double minCost(int[] cityX, int[] cityY, double roadCost, double airportCost) | | (be sure your method is public) |
|
| |
|
| |
Constraints |
| - | cityX will have between 1 and 150 elements, inclusive. |
| - | cityY will have the same number of elements as cityX. |
| - | Each element of cityX and cityY will be between 0 and 1000000, inclusive. |
| - | roadCost will be between 0 and 3.0, inclusive. |
| - | airportCost will be between 0 and 10000000, inclusive. |
| - | The locations of the cites will be distinct. |
| |
Examples |
| 0) | |
| | {0, 0, 400, 400} | {0, 100, 0, 100} | 1.0 | 150.0 |
| Returns: 500.0 | | An optimal transportation network would be:
- Build roads connecting city 0 with city 1 and city 2 with city 3.
- Build airports at cities 0 and 2. |
|
|
| 1) | |
| | {0, 0, 400, 400, 2000} | {0, 100, 0, 100, 2000} | 1.0 | 500 |
| Returns: 1600.0 | |
|
| 2) | |
| | {0, 100, 200, 300, 400,2000,2100,2200} | {0, 100, 200, 300, 400,2000,2100,2200} | 0.5 | 200 |
| Returns: 824.2640687119285 | |
|
| 3) | |
| | {798, 915, 797, 463, 895, 523, 959, 702, 235, 523} | {126, 25, 402, 45, 841, 762, 982, 605, 616, 78} | 1.66 | 300 |
| Returns: 2727.2895312339606 | |
|