| Getting There |
A frustrating part of arranging your own air travel trip is selecting from among many possible flights that sequence of flights which will take you from your origin to your destination in the least possible time or for the least possible cost.
It should be clear to any frequent air passenger that in order to reach one city from another, the cost of the shorter flight may be more than the cost of longer flights. In other words, it may pay you well to cool your heels in an airport waiting for a connecting flight rather than take a more direct flight or one in which the connecting time is shorter. For example, consider the following flight schedule.
Center City Homeville 5:2OA 6:55A 12.50
Center City Greenville 5:45A 9:l5A 35.00
Homeville Greenville 7:45A 9:35A 20.00
In order to travel from Center City to Homeville, you have two choices. You can travel from Center City to Homeville, then from Homeville to Greenville, or you can travel directly from Center City to Greenville. The first route costs $32.50 and has travel time 4:15; the direct route costs $35.00 and has travel time 3:30. If minimizing cost is your objective, then you would choose the first route. If you want to minimize time, you would select the second route.
You are to write a program to optimize route selection given the criteria of least cost or least time. Your program will read a list of flights and several trip rcquests and will select from the list of flights the best sequence to satisfy each trip request. For each request, if more than one route should satisfy the request, then your program should select the route that also satisfies the other objective. For example, if cost is to be minimizad and if two routes both yield the minimum cost, then select the route which yields the shortest travel time. If two routes yield identical costs and travel times, then select either route.
The input data file is broken into two segments, the first describing the list of flights and the last containing the trip requests. The end of this part of the file is indicated by the line consisting of the single character `#'.
The flight segment of the file describes individual flights, one per line. Each line contains the origin city (columns 1 through 20), the destination city (columns 21 through 40), the departure time (columns 41 through 47). the arrival time (columns 48 through 54), and the cost (columns 55 through 60). City names are left-justified in their respective fields, and may contain upper and lower case characters. Times are in the form HH:MMX, where HH is the hour (a leading zero may be replaced by a blank), MM is the minutes (exactly two digits will appear), and X is A (for AM), P (for PM), or M or N (used only after 12:00 to distinguish midnight from noon). The cost of the ticket is in dollars and cents, and includes a decimal point and two fractional digits. No tickets are free or cost more than $999.99. Departure times are always prior to arrival times. No individual flight represented by a line in the schedule takes more than 24 hours. There will be at most 20 flights on the schedule.
The trip request segment of the file immediately follows the list of flights. Each request appears on a line by itself, and specifies the origin city (columns 1 to 20), the destination city (columns 21 to 40), and whether to optimize cost or travel time. If it is desired to optimize travel time, the word TIME is in columns 41 to 44. If cost is to be optimized, then the word COST is in columns 41 to 44. There may be trailing blanks in any line in the flight schedule or the trip requests. The end-of-file indicates the end of the trip requests.
For each travel request, display the request and the optimal route in the form shown below.
The last line gives the travel time in days, hours, and minutes, and the total cost of the trip. All optimum routes will require less than 10 days and less than $1,000.00. Place one blank line between the outputs for successive trips.
Center City Homeville 5:2OA 6:55A 12.50 Center C¡ty Greenville 5:45A 9:l5A 35.00 Homeville Greenville 7:45A 9:35A 20.00 Archer City Homeville 5:OOA 6:OOP 612.50 # Center City Greenville COST Archer City Greenville TIME
From: Center City To: Greenville Optimize: Cost
==================================================================
From To Leave Arrive Cost
==================================================================
Center City Homeville 5:20A 6:55A $12.50
Homeville Greenville 7:45A 9:35A $20.00
-----------------------
4:15 $32.50
From: Archer City To: Greenville Optimize: Time
==================================================================
From To Leave Arrive Cost
==================================================================
Archer City Homeville 5:00A 6:00P $612.50
Homeville Greenville 7:45A 9:35A $20.00
-----------------------
1 day 4:35 $632.50