Programming Contest Finals

sponsored by

Problem E
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.

A driver's normal workday will not exceed 10 hours.
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.
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.
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.
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.

Input

Input for each scenario comes in two parts: a list of the bags and a table of times required to drive between stations. The first line in each scenario consists of an integer n representing the number of bags to be delivered. The next n lines describe each bag in the following format:

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

Output for each scenario begins by identifying the scenario by number (Scenario 1, Scenario 2, etc.). Following that is a listing of each driver's optimal route. Each route begins with the number of the driver (Driver 1, Driver 2, etc.) and then a summary of the driver's route including all transits between stations in the order in which the stations were visited. For transits which deliver a bag, display the bag identification number and its origin and destination stations For transits which do not deliver a bag, display the origin and destinations stations. 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.

Sample Input

Output for the Sample Input

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

This page maintained by Ed Karrels.
Last updated November 6, 1997