Minimum Cost Rail Travel
Wilson has fixed an appointment with his business Client at a faraway City. He is a disciplined person and he schedules his appointments well thought-out. Hence he decided to plan his travel by rail and intended to book his rail ticket much in advance.Wilson knew that the cost of a ticket is determined by numerous factors, and is usually not directly related to the distance traveled. Most of the travelers try to use only parts of tickets with stops in various cities to achieve minimum cost travel. However, the ticket issuing authorities are aware of this behavior, and usually require that the travel covered by a ticket be completed in order and without intervening travel.
Instance if a traveler has a ticket for travel from City-1 to City-2 then to City-3, he is not allowed to use only the portion of the ticket for travel from City-2 to City-3. He must always start at the first city on the ticket. In addition, he is not allowed to travel from City-1 to City-2, fly elsewhere and return, and then continue your journey from City-2 to City-3.
Wilson wanted to determine how good he can purchase the tickets in order to minimize the cost of travel provided each trip will be possible.
Example:
Suppose Wilson is allowed to purchase three types of tickets:
Ticket #1: City-1 to City-2 to City-3 $225
Ticket #2: City-1 to City-2 $200
Ticket #3: City-2 to City-4 $50
He wanted to travel from City-1 to City-4. There are two ways to get there using only the available ticket choices:
i) Purchase Ticket #1 for $225 and use only the first leg of the ticket, then Purchase Ticket #3 for $50 and reach City-4. So cost of travel from City-1 to City-4 is $275.
ii) Purchase Ticket #2 for $200 and Ticket #3 for $50. So cost of travel from City-1 to City-4 is $250.
Of this the second choice is the cheapest. So the result will be $250 #2 #3. (Follow the purchase order of tickets).
Given the scenario:
If there are 6 types of tickets. And the Tickets are as follows:
Ticket #1: City-1 to City-2 to City-3 $150
Ticket #2: City-1 to City-4 $200
Ticket #3: City-1 to City-3 to City-6 $100
Ticket #4: City-3 to City-6 $300
Ticket #5: City-2 to City-5 to City-4 $250
Ticket #6: City-3 to City-6 $260
He wanted to travel from City-1 to City-2 to City-4.
What is the cheapest choice of tickets. (Type in the numbers separated by a space in the below textbox Example : $200 #2 #3).
ANSWER $150 #5 #2
No comments: