Problem Statement |
| | A traveling salesman wants to survey N cities for business opportunities. The cities are numbered 0 through N-1, and he wishes to visit each of them at least once. He starts at city 0 and can end at any city. There are several bidirectional roads, each connecting two different cities and costing some amount of money to traverse.
The traveling salesman also has a time machine. He can use the time machine to go back in time, without affecting which cities he is considered to have already visited. For example, suppose he has visited cities A, B, C, D, and E, in that order, and is currently in city E. He can use the time machine to go back to city A, B, C, or D. Suppose he chooses to go back to city C. At that point, he can then go back further to city A or B, but he cannot use the time machine to go forward to city D or E. Note that going back in time will not change the fact that he is considered to have already visited cities A, B, C, D, and E.
You are given the roads in the String[] roads. Concatenate the elements of roads, in order, to get a single space-separated list of roads. Each road will be formatted "a,b,travelcost" (quotes for clarity), which means that the bidirectional road connects city a and city b, and costs travelcost to traverse.
He can use the time machine any number of times, and it costs nothing to use it. Return the minimum cost required to visit all the cities. Return -1 if it is impossible to visit all the cities. |
| |
Definition |
| | | Class: | TimeTravellingSalesman | | Method: | determineCost | | Parameters: | int, String[] | | Returns: | long | | Method signature: | long determineCost(int N, String[] roads) | | (be sure your method is public) |
|
| |
|
| |
Constraints |
| - | N will be between 2 and 1000, inclusive. |
| - | roads will contain between 1 and 50 elements, inclusive. |
| - | Each element of roads will contain between 1 and 50 characters, inclusive. |
| - | Each character in roads will be '0'-'9', ',' or ' '. |
| - | roads will be formatted as described in the problem statement without leading or trailing spaces. |
| - | All integers in the concatenation of all the elements of roads in the order they are given will have no extra leading zeroes. |
| - | In each road, a and b as described in the problem statement will be different and will each be between 0 and N-1, inclusive. |
| - | In each road, travelcost as described in the problem statement will be between 1 and 10,000,000, inclusive. |
| - | For each two different cities, there will be at most one road connecting them. |
| |
Examples |
| 0) | |
| | | Returns: 2 | | Travel from city 0 to city 1. Go back in time to city 0. Travel from city 0 to city 2. The total cost is 1+1=2. |
|
|
| 1) | |
| | 6 | {"0,1,2 1,4,2 4,3,3 2,4,4 0,5,3"} |
| Returns: 14 | | Travel from city 0 to city 1 to city 4 to city 3. Go back in time to city 4. Travel from city 4 to city 2. Go back in time to city 0. Travel from city 0 to city 5. The total cost is 2+2+3+4+3=14. |
|
|
| 2) | |
| | | Returns: -1 | | It is impossible to reach city 1. |
|
|
| 3) | |
| | 4 | {"1,0",",10","0 2,1",",584 3,2",",754"} |
| Returns: 1438 | |
|