当前你的浏览器版本过低,网站已在兼容模式下运行,兼容模式仅提供最小功能支持,网站样式可能显示不正常。
请尽快升级浏览器以体验网站在线编辑、在线运行等功能。

建议使用的浏览器:

谷歌Chrome 火狐Firefox Opera浏览器 微软Edge浏览器 QQ浏览器 360浏览器 傲游浏览器

2324:Catch the Bus!

题目描述
ACM needs to deliver marketing materials to one of their clients. Both ACM and the client employ students to make such deliveries. And these students use public buses to move throughout the city. Sometimes, it is necessary to pass the materials as fast as possible.

You are given bus timetables and your task is to find the fastest way for two students to meet at some stop. The place of the meeting is not important, they only need to meet as early as possible.

Students may change between any two bus routes at stops that are common for both routes. At least two minutes are needed for every such change. No additional time is necessary to get on the first bus or to meet the other student in the target stop.
输入解释
The input contains a sequence of several scenarios, the sequence is terminated by a line containing negative number.

Each scenario begins with a non-negative integer L, the number of bus routes that operate in the city (L ≤ 1000). Every route is then described by two lines. The first line contains names of stops that the bus runs through. Between each consecutive stops, there is a non-negative integer specifying the number of minutes required to travel between these stops with the given bus. The last stop is followed by a negative number.

The second line of each bus route contains non-negative integers separated with spaces. The first integer H gives the number of buses that depart the initial stop in every hour (H ≤ 60). The remaining H integers are always distinct and sorted ascendingly, they list the minutes of departure (between 0 and 59). The timetable repeats every hour. For example, if the second line says “2 00 30”, the buses leave the initial stop at 12:00, 12:30, 13:00, 13:30, 14:00, etc.

After the description of routes, there are two lines that specify the initial position of students. Each of them will contain time in a standard 24-hour format (one or two digits for hours, colon, and two digits for minutes) and a stop name.

All numbers, times, and stop names will be separated with a single space. Stop names are case-sensitive and may be composed only from lower-case and upper-case letters, their length will not exceed 30 characters. The total number of stops will be at most 1000, the number of stops on a single route will not exceed 100. The time between any two consecutive stops will be at most one hour. The routes are considered one-way, if they operate in both directions, they will be given as two separate routes. A route may run through the same stop several times.
输出解释
For each test scenario, output a single line containing the earliest possible time the students can meet at any of the stops. The time must appear in the standard 24-hour format, hours given as a number between 0 and 23, then colon and minutes between 0 and 59. For hour values less than 10, only one digit must be used. Be aware of the fact that both students start their trip on the same day but may meet on another day, if the required time exceeds midnight.

If the students are not able to meet in some scenario, output the words “No connection” instead of the time.
输入样例
4
Hradcanska 2 Malostranska 2 Staromestska 2 Mustek 1 Muzeum -1
10 00 06 12 18 24 30 36 42 48 54
Muzeum 1 Mustek 2 Staromestska 2 Malostranska 2 Hradcanska -1
10 03 09 15 21 27 33 39 45 51 57
Andel 2 Karlovo 1 Narodni 2 Mustek 2 Florenc -1
6 00 10 20 30 40 50
Florenc 2 Mustek 2 Narodni 3 Karlovo 1 Andel -1
6 02 12 22 32 42 52
12:00 Hradcanska
12:11 Andel
1
Hradcanska 2 Malostranska 2 Staromestska 2 Mustek 1 Muzeum 2 Hradcanska -1
10 00 06 12 18 24 30 36 42 48 54
12:00 Mustek
12:00 Andel
-1
输出样例
12:20
No connection
来自杭电HDUOJ的附加信息
Recommend teddy

该题目是Virtual Judge题目,来自 杭电HDUOJ

题目来源 CTU Open Contest 2007

源链接: HDU-2324

最后修改于 2020-10-25T22:52:32+00:00 由爬虫自动更新

共提交 0

通过率 --%
时间上限 内存上限
6000/2000MS(Java/Others) 65536/32768K(Java/Others)