2007/2008 SOUTHERN CALIFORNIA REGIONAL
ACM INTERNATIONAL COLLEGIATE PROGRAMMING CONTEST

Problem E
Swamp Trompin'

Swamp County has historically poor transportation infrastructure, and many residents lack automobiles. Public transportation serving Swamp County is incomplete and often inconvenient. As a result, citizens have been forced to improvise unique combinations of transportation to get where they need to go. Locals call this off-beat tradition "Swamp Trompin'."
For example, the daily routine of one inventive resident consists of: biking from home to the edge of nearby Lake Swampy, standing on a log and poling across the shallow lake, hiking to the bus stop on Bog Street and waiting for the Route 32 bus, riding that bus to the Crayfish Avenue stop, waiting there for the Dragonfly Trolley, riding the trolley to the Broken Oak Street stop, cutting through the Broken Oak Bait and Feed shopping mall, roller-blading from the mall parking lot across the traffic intersection crosswalk at Weeping Willow Lane, and finally arriving at work with eight minutes to spare.
Given an origin, a destination, a needed arrival time, and a list of available route segments, your team is to develop a program that will find a route that allows the traveler to start at the latest possible time and still reach the destination by the needed arrival time.
Input to your program will begin with three lines containing the name of the origin, the name of the destination, and the needed arrival time in that order. Each of these values will begin in the first column and will not contain trailing whitespace.
The remaining input will be a list of route segments. Each route segment consists of an action description, a start point name, end point name, an integer traversal time in minutes, and an availability specification that describes the times at which that segment may be used. The availability specification consists a start time and end time (both inclusive), and an integer number of minutes indicating the interval between possible departures. All fields are separated by commas. All times are written as HH:MM in a 24-hour format. For example, if a bus's availability is "09:00,12:00,40" that means that the bus departs the segment starting point at 09:00, 09:40, 10:20, 11:00, and 11:40. An interval value of 1 is used for all pedestrian segments to indicate that the traveler may start walking at any minute of the day. The input will contain between 1 and 100 route segments and is terminated by end-of-file. Route segments may appear in any order.
You may assume that the traveler has enough money to pay for any fares, and that he or she carries any equipment needed for any route segment (e.g., a bicycle) and can use it without delay (e.g., no time is needed to put on roller-blades). The shortest duration needed to traverse any segment is 1 minute. The traveler may wait at any location for any number of minutes. Buses and other public transportation always run on time, are never full, and follow the same schedule every day. All traveling takes place between the hours of 6 AM and noon. Availability specifications may cover any time of day, but times do not span midnight.
Your program should print step-by-step directions giving the start time of each action, as shown in the sample output. Times are to be printed in the same format as used in the input. Waiting time is implied-do not print waiting time in the directions. The last step should be the time of arrival at the destination. If there is no way for the traveler to begin at 6 AM or later and reach the destination by the needed arrival time, your program should print "Just stay home". If there are multiple routes that require the traveler to begin at the same time, print the route that reaches the destination soonest. If there are multiple routes that start and end at the same times, print any one of them.
Sample Input

 Home
 Work
 10:00
 Bike,Home,Lake Swampy East Shore,15,00:00,23:59,1
 Push a log,Lake Swampy East Shore,Lake Swampy West Shore,6,00:00,11:59,1
 Push a log,Lake Swampy West Shore,Lake Swampy East Shore,8,00:00,11:59,1
 Hike,Lake Swampy West Shore,Bog Street,19,00:00,23:59,1
 Ride Route 32 Bus,Gater Gully,Bog Street,15,06:30,18:15,20
 Ride Route 32 Bus,Bog Street,Crayfish Avenue,10,06:45,18:15,20
 Ride Dragonfly Trolley,Crayfish Avenue,Broken Oak Street,12,08:00,18:00,30
 Ride Dragonfly Trolley,Broken Oak Street,Motorsport arena,23,08:12,17:12,30
 Mall Walk,Broken Oak Street,Parking lot,5,09:00,18:00,1
 Roller-blade across crosswalk,Parking lot,Weeping Willow Lane,1,00:00,23:59,2
 Walk,Weeping Willow Lane,Work,3,00:00,23:59,1
 Hike,Home,Work,240,00:00,23:59,1
 Roller-blade,Home,Work,300,00:00,23:59,1


Output for the Sample Input

 08:25 Bike from Home to Lake Swampy East Shore
 08:40 Push a log from Lake Swampy East Shore to Lake Swampy West Shore
 08:46 Hike from Lake Swampy West Shore to Bog Street
 09:05 Ride Route 32 Bus from Bog Street to Crayfish Avenue
 09:30 Ride Dragonfly Trolley from Crayfish Avenue to Broken Oak Street
 09:42 Mall Walk from Broken Oak Street to Parking lot
 09:48 Roller-blade across crosswalk from Parking lot to Weeping Willow Lane
 09:49 Walk from Weeping Willow Lane to Work
 09:52 Arrive at Work



File translated from TEX by TTH, version 3.77.
On 18 Nov 2007, 09:01.