Catch the Bus!
Time limit1sMemory limit128 MB
Given bus routes with hourly timetables and two students' start times and stops, find the earliest moment they can meet at any shared stop, considering 2-minute transfer times.
- Level
Hard8 of 10
- Topics
- Shortest path, Graph, Simulation, Implementation
- Solved
- No attempts yet
Problem
ACM needs to deliver marketing materials to one of their clients. Both ACM and the client employ students to make the deliveries, and these students travel around the city by public bus. Sometimes the materials must be handed over as fast as possible.
You are given the city's bus timetables. Find the earliest moment at which two students can meet at some stop. The meeting place does not matter — they only need to meet as early as possible.
A student may transfer between two bus routes at any stop the routes have in common. Every transfer takes at least 2 minutes. Boarding the very first bus takes no extra time, and meeting the other student at the target stop takes no extra time either.
Input
The input contains several scenarios, one after another. The sequence ends with a line containing a negative number.
Each scenario begins with a non-negative integer , the number of bus routes operating in the city (). Each route is then described by two lines.
- The first line lists the stops the bus runs through. Between every two consecutive stops there is a non-negative integer, the number of minutes needed to travel between them on that bus. A negative number follows the last stop.
- The second line starts with a non-negative integer , the number of buses that leave the initial stop each hour (). The remaining integers are distinct and sorted in increasing order; they are the departure minutes (from to ). The timetable repeats every hour. For example,
2 00 30means buses leave the initial stop at 12:00, 12:30, 13:00, 13:30, 14:00, and so on.
After the routes come two lines giving the students' starting positions. Each line contains a time in the standard 24-hour format (one or two digits for the hour, a colon, and two digits for the minute) followed by a stop name.
All numbers, times, and stop names are separated by a single space. Stop names are case-sensitive, consist only of lower-case and upper-case letters, and are at most characters long. The total number of stops is at most , and a single route visits at most stops. The travel time between any two consecutive stops is at most one hour. Routes are one-way; a route that runs in both directions is given as two separate routes. A route may pass through the same stop several times.
Output
For each scenario, print a single line with the earliest time the two students can meet at any stop. Use the standard 24-hour format: the hour is a number from to , followed by a colon and the two-digit minute (from to ). Print hour values below with a single digit. Both students start on the same day, but they may meet on a later day if the required time passes midnight.
If the students cannot meet in a scenario, print No connection instead.