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.