Problem Statement |
| |
Travelling salesmen (and of course, travelling saleswomen, too) usually have lots of problems. And some of them are pretty hard to solve algorithmically. Let's take a look at one such problem.
In the country there are several towns. Let towns be their count. The towns are numbered from 0 to towns-1. Our travelling salesman wants to travel through this country. He starts his journey in the town origin and wants to end it in the town destination.
There are several means of transportation he may use. For each of them he knows the source and destination town and its cost. Furthermore, each time he enters a town, he will be able to sign some contracts there and make some money. This amount of money may differ from town to town, but for each town it is a fixed amount. He does sign contracts at the beginning of his journey (in the town origin). Of course, the salesman's goal is to maximize the amount of money he has at the end of his journey.
The various travel possibilities are given in a String[] travelCosts, and the profits for each town are given in a int[] profits. Each element of travelCosts is of the form "SOURCE DESTINATION COST", where SOURCE and DESTINATION are town numbers and COST is the cost of using this transportation. In profits there are exactly towns elements, and the i-th of them is the amount of money gained when entering town i.
If it is not possible to reach the destination town at all, return the String "IMPOSSIBLE".
If it is possible to reach the destination town with an arbitrarily large final profit, return the String "ENDLESS PROFIT".
Otherwise, return the String "BEST PROFIT: X", where X is the best profit he can make.
The value X must be printed with no unnecessary leading zeroes.
|
| |
Definition |
| | | Class: | SalesmansDilemma | | Method: | bestRoute | | Parameters: | int, int, int, String[], int[] | | Returns: | String | | Method signature: | String bestRoute(int towns, int origin, int destination, String[] travelCosts, int[] profits) | | (be sure your method is public) |
|
| |
|
| |
Notes |
| - | We are interested in the amount the salesman earns during the journey, i.e., the difference between the balance of his account at the end and at the beginning of his journey. This difference may also be negative in case the salesman has to pay more than he earns during his journey. |
| - | The salesman may travel to the same town multiple times. He gains the profit from the town once for each visit he makes. |
| - | All means of transportation can only be used in the specified direction, i.e., they are one-way. The salesman may use each of them multiple times. |
| |
Constraints |
| - | towns is between 1 and 50, inclusive. |
| - | origin and destination are between 0 and towns-1, inclusive. |
| - | profits has exactly towns elements. |
| - | Each element of profits is between 0 and 1,000,000, inclusive. |
| - | travelCosts has between 1 and 50 elements, inclusive. |
| - | Each element of travelCosts is of the form "SOURCE DESTINATION COST". |
| - | Each SOURCE and DESTINATION in travelCosts are integers between 0 and towns-1, inclusive, with no unnecessary leading zeroes. |
| - | Each COST in travelCosts is an integer between 1 and 1,000,000, inclusive, with no leading zeroes. |
| |
Examples |
| 0) | |
| | 5 | 0 | 4 | {"0 1 10", "1 2 10", "2 3 10", "3 1 10", "2 4 10"} | {0, 10, 10, 110, 10} |
| Returns: "ENDLESS PROFIT" |
The profit in each town exactly covers the cost of travelling there. The single exception is town 3. Each time the salesman travels (from town 2) to town 3, he pays 10 for the travel and gains 110 from sales in town 3, resulting in a net gain of 100.
He is able to reach an arbitrarily large profit in the following way:
Start by travelling from 0 to 1, travel around the circle 1->2->3->1 sufficiently many times, then travel from 1 to 2 and from 2 to 4.
|
|
|
| 1) | |
| | 5 | 0 | 4 | {"0 1 13", "1 2 17", "2 4 20", "0 3 22", "1 3 4747", "2 0 10", "3 4 10"} | {0, 0, 0, 0, 0} |
| Returns: "BEST PROFIT: -32" | | There is no profit here, so the salesman has to find the cheapest way of travelling. |
|
|
| 2) | |
| | 3 | 0 | 2 | {"0 1 10", "1 0 10", "2 1 10"} | {1000, 1000, 47000} |
| Returns: "IMPOSSIBLE" | | The destination town is unreachable. |
|
|
| 3) | |
| | 2 | 0 | 1 | {"0 1 1000", "1 1 10"} | {11, 11} |
| Returns: "ENDLESS PROFIT" | |
|
| 4) | |
| | | Returns: "BEST PROFIT: 7" | | Loops are not always useful. |
|
|
| 5) | |
| | 5 | 0 | 4 | {"0 1 13", "1 2 17", "2 4 20", "0 3 22", "1 3 4747", "2 0 10", "3 4 10"} | {8, 10, 20, 1, 100000} |
| Returns: "BEST PROFIT: 99988" | |
|