Acme Courier Message, Inc. (ACM) is planning to add a service for delivery of documents and small parcels. ACM will group parcels and documents in bags, which will be transported by car among different stations for intermediate handling and routing prior to final delivery. ACM is in the initial stages of determining the workload requirements for transporting bags among stations.
When a driver delivers a bag, she will (if possible) locate and pick up another bag for delivery to another station, continuing in this manner until there are no more deliverable bags. A deliverable bag is one that can be picked up and delivered to its destination by a driver prior to the end of her workday. The total time for a driver's workday begins with the time of pickup of her first bag and includes the time she spends delivering bags, the time in transit, and the time waiting at stations for deliverable bags. ACM would like its drivers to spend the maximum amount of time possible delivering the bags between stations within a normal workday. In addition, ACM wants drivers' final destinations to be the same as the stations where they started whenever possible.
You must write a program to determine optimal driver routes for several ACM scenarios. Each scenario describes bags and stations for a single workday. In this simple version, routes for all drivers will originate from the same station, which we call station A. Optimal routes are subject to the following restrictions.
The optimal route for the driver who picks up the first available deliverable bag at station A is completely determined before any consideration of subsequent drivers. The optimal route of the second driver, who picks up the next available deliverable bag at station A that has not already been scheduled for delivery by the first driver, is completely determined next. The optimal route determination continues in this manner until all the bags that can be delivered have been scheduled for delivery. Undeliverable bags will be identified and reported. Throughout the entire process, each driver will be routed according to the bags not already scheduled earlier for delivery. In all scenarios the time to travel from station A to any other station is 10 hours or less.
id origin destination time
where id is the bag identification number (integer), origin and destination are the station labels for the bag's origin and destination (uppercase letters), and time is when the bag is available for transport. The format for time is hhmm, where hh and mm are integers representing time on a 24-hour clock varying from 0001 to 2400. Data on a line are separated by single blanks. Each station is labeled with a unique uppercase letter. Bags may appear in any time order in the list. The end of input is signified by a scenario for which the number of bags is 0.
Input data for the table of driving times consist of lines of the form:
station1 station2 time
where station1 and station2 are uppercase letters and time is as described earlier. Transit times between stations are listed for all stations which are included in the list of bags. Transit times are bidirectional. Different scenarios are completely unrelated.
Output for each driver is summarized by the total delivery time and the total workday time in the form hhmm, following the time format specified in the input of time values. If two different routes for a driver are optimal, then output may show either one. The final section of output for a scenario will include a listing of all undeliverable bags or a statement indicating successful delivery of all bags.
Each section of a scenario and each scenario should be separated by a blank line.
7 1 A B 0800 3 A C 0850 2 B C 0700 6 B D 1250 5 B C 1400 7 C A 1600 8 D C 1130 A B 0400 A C 0135 A D 0320 B C 0345 B D 0120 C D 0200 0
Scenario 1 Driver 1 Bag #1 from station A to station B Bag #2 from station B to station C Bag #7 from station C to station A Total delivery time: 0920 Total workday time: 0935 Driver 2 Bag #3 from station A to station C -->Transit without delivery from station C to station B Bag #5 from station B to station C Total delivery time: 0520 Total workday time: 0905 Undelivered Bags: Bag #8 remains at station D Bag #6 remains at station B