1998 Northeast U.S. Regional Programming Contest
Problem 4: We Ship Cheap
jumpship.cc
The JumpShip package shipping company is always interested in reducing
their costs. JumpShip delivers packages among a number of cities by tying
them to the landing gear of unsuspecting FedEx and UPS aircraft. Because
of pesky security issues, JumpShip does not guarantee that they will be
able to get a package from city A to city B in a single trip; often, they
must send a package through intermediate points where fewer people are
watching... .
In any case, JumpShip "borrows" the weekly security schedules from FedEx
and UPS each Sunday in order to plan efficient routes for its customers'
packages in the upcoming week. From the schedule, they determine which
routes will be accessible for use. Your task is then to compute how many
flights are required for a particular package to be sent from one city
to another.
Input
The input file to your program consists of two parts. On the first line
there is an integer indicating the number of departure cities available.
Then, there are that many lines, each beginning with the airport code of
a departure city, followed by the destination airports reachable in a single
flight from that departure city (separated by whitespace). After this set
of available flights appear queries, one per line. Each query consists
of two cities, and the program must compute the number of flights required
to get a package from the first to the second city, using only flights
available in the original schedule.
Output
The output should consist of one integer for each query -- indicating the
number of flights required to get a package from start to finish. If it
is not possible to get a package from the first city to the second, you
should print the line "Try again next week." instead.
Sample input:
3
LGA JFK LAX ORD
ORD EVV LIM
LIM LAX LGA
LIM EVV
JFK LGA
ORD ORD
LGA LIM
Sample output:
3
Try again next week.
0
2