Optimal Routing |

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.

- 1.
- A driver's normal workday will not exceed 10 hours.
- 2.
- Drivers will travel from one station to another with one bag, if one is available for pickup. If there are no deliverable bags at a station, the driver will proceed to another station that has a scheduled deliverable bag to continue her route.
- 3.
- If several different routes with a final destination of station A are possible, the one requiring the longest cumulative delivery time is optimal. If there are more than one with the longest cumulative delivery time, the one with the shortest total workday time is optimal.
- 4.
- Whenever possible, the final destination of a driver is station A. However, if it is impossible to schedule a final destination of station A, then the route requiring the longest cumulative delivery time is optimal. If there are more than one with the longest cumulative delivery time, the one with the shortest total workday time is optimal.
- 5.
- Every bag that originates from station A will be delivered. (Some bags originating at other stations will not necessarily be delivered.) No bag will be delivered more than once.

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