Problem Statement |
| | The king loves his queen a lot, and he wants to take her all over the kingdom, in just a single day.
The kingdom has N cities in it. There are bi-directional roads connecting the cities such that there is a unique path from any city in the kingdom to any other city. Each road has an integral length.
The king wants to take his queen on a tour in the kingdom which starts and ends at the kingdom's capital. Since the kingdom is really beautiful, the king wants the tour to cover each road in the kingdom at least once (it doesn't matter in which direction). However, he has been informed that this might take a really long time. Hence, he has decided to build at most K shortcuts. A shortcut can connect any two cities (even if they are directly connected by a road), and the length of a shortcut is L. Since the scenery around the newly constructed shortcuts might not be so beautiful, the king has demanded that any particular shortcut cannot be taken more than once during the tour.
The cities in the kingdom are numbered 0 to N-1. City 0 is always the capital. The roads of the kingdom are described in String[] roads. Concatenate the elements of roads to get a single String. This String is a comma separated list of the roads in the kingdom in the form "A B C" (quotes for clarity), meaning that there is a road of length C connecting city A and city B.
Return the length of the shortest tour satisfying the king's demands.
|
| |
Definition |
| | | Class: | KingdomTour | | Method: | minTime | | Parameters: | int, String[], int, int | | Returns: | int | | Method signature: | int minTime(int N, String[] roads, int K, int L) | | (be sure your method is public) |
|
| |
|
| |
Constraints |
| - | N will be between 2 and 200, inclusive. |
| - | K will be between 0 and 100, inclusive. |
| - | roads will contain between 1 and 50 elements, inclusive. |
| - | Each element of roads will contain between 1 and 50 characters, inclusive. |
| - | roads, when concatenated, will be a comma-separated list of roads, where each road is formatted "A B C" (quotes for clarity). |
| - | In each road "A B C", A and B will be distinct integers between 0 and N-1, inclusive, with no extra leading zeroes, and C will be an integer between 1 and 10000, inclusive, with no leading zeroes. |
| - | The roads will be such that the kingdom will satisfy the properties mentioned in the problem statement. |
| - | L will be between 1 and 10000, inclusive. |
| |
Examples |
| 0) | |
| | | Returns: 16 | | If a shortcut is constructed from city 0 to city 2, then the tour 0-->1-->2-->0 has a length of 16 units. |
|
|
| 1) | |
| | | Returns: 7 | | Construct a shortcut between the only two existing cities. Traverse the road once, and use the shortcut once. |
|
|
| 2) | |
| | 6 | {"4 0 4,2 0 4,2 5 4,4 3 1",
"0,1 2 10"} | 2 | 5 |
| Returns: 41 | | Make sure you concatenate the elements of roads[]. |
|
|
| 3) | |
| | 10 | {"1 2 2,4 1 9,2 5 5,6 5 4,", "1 7 7,7 3 1,2 0 2", ",5 8 5,9 5 6"} | 2 | 4 |
| Returns: 59 | |
|