39. Mr. Rabbit and Metro

单点时限: 8.0 sec

内存限制: 256 MB

上海地铁的末班车早得世界闻名。

作为码农,瑞比先生经常加班,经常要赶末班车。他现在希望你帮忙计算一下回家需要多少时间,免得 Mrs. Bunny 担心。

有关上海地铁的操作规则,我想大家都已经很熟悉了。这里有几点再要说明一下:

  • 每一条地铁线路,都有其独立的运行时间间隔、末班车时间和途径车站。
  • 如果两条不同地铁线路的某一个途径车站同名,则在该站可以换乘。换乘需要消耗3分钟
  • 当然也可以选择从一个地铁站步行到另一个地铁站,步行时间为在坐地铁的情形下所需要的最少时间乘上 7。另外,既然都已经步行了,就不用考虑换乘和等地铁的时间了。如果从 A 到 B 有多条线路可以到达,取其中耗时最短的那一条。并且,从 A 站到 B 站和从 B 站到 A 站所需的时间有可能不同。
  • 步行状态和乘地铁状态之间的转换不耗时。
  • 如果起始站是换乘车站,可以从任意一个入口进入地铁;目的地亦然。
  • 为了方便理解,地铁运行的很多细节都被略去了:例如,10、11号线等线路的支线被略去,4号线被改成了普通的双向线路,而不再是环线。请以读入数据为准。

输入格式

第一行一个整数,表示地铁线路数。

对于每一条线路,首先是三个整数,分别为线路编号、发车间隔和经停站数,然后接下来每一行分别是站名、正向经过的末班车时间、反向经过的末班车时间。

然后是一行一个整数,表示查询数目 $Q$ $(1 \leq Q \leq 300)$。每次查询提供出发站名,目的地站名,和出发时间 (HH:MM)。出发时间晚于 12:00,早于 24:00。

输出格式

对于每个询问,输出一行:最少需要的时间(单位:分钟)。

输入保证有解。

样例

Input
14
1 4 28
XinZhuang 22:32 23:34
WaiHuanLu 22:34 23:32
LianHuaLu 22:36 23:30
JinJiangLeYuan 22:39 23:27
ShangHaiNanZhan 22:42 23:24
CaoBaoLu 22:45 23:21
ShangHaiTiYuGuan 22:48 23:19
XuJiaHui 22:50 23:16
HengShanLu 22:52 23:14
ChangShuLu 22:54 23:12
ShanXiNanLu 22:56 23:10
HuangBeiNanLu 22:58 23:08
RenMinGuangChang 23:01 23:05
XinZhaLu 23:03 23:03
HanZhongLu 23:05 23:01
ShangHaiHuoCheZhan 23:08 23:00
ZhongShanBeiLu 23:10 22:57
YanChangLu 23:13 22:55
ShangHaiMaXiCheng 23:15 22:53
WenShuiLu 23:17 22:50
PengPuXinCun 23:20 22:47
GongKangLu 23:23 22:45
TongHeXinCun 23:25 22:42
HuLanLu 23:27 22:40
GongFuXinCun 23:30 22:37
BaoAnGongLu 23:33 22:34
YouYiXiLu 23:35 22:32
FuJinLu 23:37 22:30
2 4 22
GuangLanLu 22:50 23:42
JinKeLu 22:53 23:40
ZhangJiangGaoKe 22:55 23:37
LongYangLu 22:59 23:33
ShiJiGongYuan 23:01 23:31
ShangHaiKeJiGuan 23:04 23:29
ShiJiDaDao 23:07 23:26
DongChangLu 23:10 23:24
LuJiaZui 23:12 23:22
NanJingDongLu 23:15 23:19
RenMinGuangChang 23:18 23:17
NanJingXiLu 23:21 23:14
JingAnSi 23:24 23:12
JiangSuLu 23:26 23:09
ZhongShanGongYuan 23:29 23:07
LouShanGuanLu 23:32 23:04
WeiNingLu 23:35 23:01
BeiXinJing 23:38 22:59
SongHongLu 23:40 22:57
HongQiaoErHaoHangZhanLou 23:47 22:50
HongQiaoHuoCheZhan 23:49 22:48
XuJingDong 23:51 22:45
3 7 29
ShangHaiNanZhan 22:30 23:42
ShiLongLu 22:32 23:40
LongCaoLu 22:35 23:38
CaoXiLu 22:37 23:36
YiShanLu 22:39 23:33
HongQiaoLu 22:41 23:31
YanAnXiLu 22:44 23:29
ZhongShanGongYuan 22:46 23:27
JinShaJiangLu 22:48 23:24
CaoYangLu 22:50 23:22
ZhenPingLu 22:53 23:20
ZhongTanLu 22:55 23:17
ShangHaiHuoCheZhan 22:58 23:15
BaoShanLu 23:01 23:11
DongBaoXingLu 23:03 23:09
HongKouZuQiuChang 23:06 23:07
ChiFengLu 23:08 23:04
DaBaiShu 23:10 23:02
JiangWanZhen 23:13 23:00
YinGaoXiLu 23:15 22:57
ChangJiangNanLu 23:18 22:54
SongFaLu 23:20 22:51
ZhangHuaBang 23:23 22:49
SongBinLu 23:25 22:47
ShuiChanLu 23:27 22:45
BaoYangLu 23:30 22:42
YouYiLu 23:32 22:40
TieLiLu 23:34 22:37
JiangYangBeiLu 23:37 22:35
4 7 26
YiShanLu 22:30 23:30
ShangHaiTiYuGuan 22:32 23:27
ShangHaiTiYuChang 22:34 23:25
DongAnLu 22:36 23:23
DaMuQiaoLu 22:37 23:21
LuBanLu 22:39 23:19
XiZangNanLu 22:42 23:17
NanPuDaQiao 22:44 23:15
TangQiao 22:47 23:12
LanCunLu 22:49 23:10
PuDianLu 22:51 23:07
ShiJiDaDao 22:53 23:05
PuDongDaDao 22:56 23:03
YangShuPuLu 22:58 23:01
DaLianLu 23:00 22:59
LinPingLu 23:02 22:57
HaiLunLu 23:04 22:55
BaoShanLu 23:07 22:52
ShangHaiHuoCheZhan 23:10 22:49
ZhongTanLu 23:13 22:46
ZhenPingLu 23:15 22:44
CaoYangLu 23:18 22:41
JinShaJiangLu 23:19 22:39
ZhongShanGongYuan 23:22 22:37
YanAnXiLu 23:24 22:35
HongQiaoLu 23:26 22:32
5 7 11
XinZhuang 22:30 22:26
ChunShenLu 22:32 22:23
YinDouLu 22:34 22:21
ZhuanQiao 22:38 22:18
BeiQiao 22:41 22:14
JianChuanLu 22:44 22:11
DongChuanLu 22:46 22:09
JinPingLu 22:49 22:07
HuaNingLu 22:51 22:04
WenJingLu 22:54 22:02
MinXingKaiFaQu 22:56 22:00
6 5 28
GangChengLu 22:30 23:35
WaiGaoQiaoBaoShuiQuBei 22:32 23:32
HangJinLu 22:35 23:30
WaiGaoQiaoBaoShuiQuNan 22:38 23:27
ZhouHaiLu 22:41 23:24
WuZhouDaDao 22:43 23:22
DongJingLu 22:45 23:20
JuFengLu 22:47 23:17
WuLianLu 22:49 23:15
BoXingLu 22:52 23:13
JinQiaoLu 22:54 23:11
YunShanLu 22:56 23:08
DePingLu 22:59 23:06
BeiYangJingLu 23:01 23:03
MinShengLu 23:03 23:01
YuanShenTiYuZhongXin 23:06 22:59
ShiJiDaDao 23:08 22:57
PuDianLu 23:11 22:54
LanCunLu 23:13 22:52
ShangHaiErTongYiXueZhongXin 23:16 22:49
LinYiXinCun 23:18 22:46
GaoKeXiLu 23:21 22:44
DongMingLu 23:23 22:41
GaoQingLu 23:26 22:39
HuaXiaXiLu 23:28 22:36
ShangNanLu 23:30 22:34
LingYanNanLu 23:32 22:32
DongFangTiYuZhongXin 23:34 22:30
7 5 33
HuaMuLu 22:30 23:33
LongYangLu 22:33 23:31
FangHuaLu 22:35 23:27
JinXiuLu 22:38 23:25
YangGaoNanLu 22:40 23:23
GaoKeXiLu 22:43 23:20
YunTaiLu 22:45 23:18
YaoHuaLu 22:47 23:16
ZhangQingLu 22:49 23:14
HouTan 22:51 23:12
LongHuaZhongLu 22:54 23:08
DongAnLu 22:56 23:06
ZhaoJiaBangLu 22:58 23:04
ChangShuLu 23:01 23:01
JingAnSi 23:03 22:59
ChangPingLu 23:06 22:57
ZhangShouLu 23:08 22:55
ZhenPingLu 23:10 22:52
LanGaoLu 23:13 22:49
XinCunLu 23:15 22:47
DaHuaSanLu 23:17 22:45
XingZhiLu 23:19 22:43
DaChangZhen 23:21 22:41
ChangZhongLu 23:24 22:39
ShangDaLu 23:26 22:36
NanChenLu 23:28 22:34
ShangHaiDaXue 23:31 22:32
QiHuaLu 23:34 22:30
GuCunGongYuan 23:37 22:26
LiuXing 23:40 22:23
PanGuangLu 23:42 22:21
LuoNanXinCun 23:46 22:17
MeiLanHu 23:48 22:15
8 5 30
ShenDuGongLu 22:30 23:35
LianHangLu 22:32 23:33
JiangYueLu 22:34 23:31
PuJiangZhen 22:36 23:29
LuHengLu 22:40 23:25
LingZhaoXinCun 22:43 23:22
DongFangTiYuZhongXin 22:47 23:19
YangSi 22:49 23:16
ChengShanLu 22:51 23:14
YaoHuaLu 22:53 23:12
ZhongHuaYiShuGong 22:55 23:10
XiZangNanLu 22:58 23:08
LuJiaBangLu 23:00 23:05
LaoXiMen 23:02 23:03
DaShiJie 23:04 23:01
RenMinGuangChang 23:06 23:00
QuFuLu 23:08 22:57
ZhongXingLu 23:10 22:55
XiZangBeiLu 23:13 22:53
HongKouZuQiuChang 23:15 22:50
QuYangLu 23:18 22:48
SiPingLu 23:20 22:46
AnShanXinCun 23:22 22:44
JiangPuLu 23:24 22:42
HuangXingLu 23:26 22:40
YanJiZhongLu 23:28 22:37
HuangXingGongYuan 23:30 22:35
XiangYinLu 23:32 22:33
NenJiangLu 23:34 22:31
ShiGuangLu 23:36 22:30
9 8 26
YangGaoZhongLu 22:30 23:10
ShiJiDaDao 22:34 23:07
ShangChengLu 22:36 23:05
XiaoNanMen 22:40 23:01
LuJiaBangLu 22:43 22:58
MaDangLu 22:45 22:56
DaPuQiao 22:47 22:54
JiaShanLu 22:49 22:52
ZhaoJiaBangLu 22:51 22:49
XuJiaHui 22:54 22:47
YiShanLu 22:57 22:44
GuiLinLu 23:00 22:40
CaoHeJingKaiFaQu 23:03 22:37
HeChuanLu 23:05 22:34
XingZhongLu 23:08 22:31
QiBao 23:11 22:28
ZhongChunLu 23:14 22:26
JiuTing 23:18 22:22
SiJing 23:24 22:15
SheShan 23:29 22:11
DongJing 23:32 22:08
SongJiangDaXueCheng 23:36 22:03
SongJiangXinCheng 23:40 22:00
SongJiangTiYuZhongXin 23:43 21:57
ZuiBaiChi 23:46 21:54
SongJiangNanZhan 23:49 21:50
10 6 24
XinJiangWanCheng 22:00 22:57
YinGaoDongLu 22:01 22:55
SanMenLu 22:03 22:53
JiangWanTiYuChang 22:06 22:51
WuJiaoChang 22:07 22:49
GuoQuanLu 22:09 22:47
TongJiDaXue 22:11 22:45
SiPingLu 22:13 22:43
YouDianXinCun 22:15 22:41
HaiLunLu 22:17 22:39
SiChuanBeiLu 22:19 22:37
TianTongLu 22:21 22:35
NanJingDongLu 22:23 22:34
YuYuan 22:26 22:31
LaoXiMen 22:28 22:28
XinTianDi 22:30 22:26
ShanXiNanLu 22:33 22:24
ShangHaiTuShuGuan 22:35 22:21
JiaoTongDaXue 22:37 22:19
HongQiaoLu 22:40 22:17
SongYuanLu 22:41 22:15
YiLiLu 22:43 22:13
ShuiChengLu 22:45 22:11
LongXiLu 22:47 22:08
11 5 28
DiShiNi 22:30 23:39
KangXinGongLu 22:34 23:34
XiuYanLu 22:37 23:31
LuoShanLu 22:40 23:28
YuQiao 22:43 23:25
PuSanLu 22:47 23:21
SanLinDong 22:50 23:18
SanLin 22:52 23:16
DongFangTiYuZhongXin 22:57 23:11
LongYaoLu 23:00 23:08
YunJinLu 23:02 23:06
LongHua 23:04 23:04
ShangHaiYouYongGuan 23:06 23:02
XuJiaHui 23:10 22:58
JiaoTongDaXue 23:12 22:56
JiangSuLu 23:16 22:53
LongDeLu 23:18 22:50
CaoYangLu 23:21 22:48
FengQiaoLu 23:22 22:46
ZhenRu 23:25 22:44
ShangHaiXiZhan 23:27 22:41
LiZiYuan 23:30 22:39
QiLianShanLu 23:32 22:36
WuWeiLu 23:34 22:34
TaoPuXinCun 23:37 22:32
NanXiang 23:41 22:28
MaLu 23:46 22:22
JiaDingXinCheng 23:50 22:19
12 6 32
JinHaiLu 22:30 23:47
ShenJiangLu 22:34 23:43
JinJingLu 22:36 23:41
YangGaoBeiLu 22:38 23:39
JuFengLu 22:41 23:36
DongLuLu 22:43 23:34
FuXingDao 22:46 23:31
AiGuoLu 22:48 23:29
LongChangLu 22:50 23:27
NingGuoLu 22:53 23:24
JiangPuGongYuan 22:55 23:22
DaLianLu 22:57 23:20
TiLanQiao 22:59 23:18
GuoJiKeYunZhongXin 23:01 23:15
TianTongLu 23:05 23:12
QuFuLu 23:07 23:10
HanZhongLu 23:10 23:07
NanJingXiLu 23:13 23:04
ShanXiNanLu 23:16 23:02
JiaShanLu 23:18 22:59
DaMuQiaoLu 23:21 22:57
LongHuaZhongLu 23:23 22:54
LongHua 23:26 22:51
LongCaoLu 23:29 22:49
CaoBaoLu 23:31 22:46
GuiLinGongYuan 23:33 22:44
HongCaoLu 23:35 22:42
HongMeiLu 23:38 22:40
DongLanLu 23:40 22:37
GuDaiLu 23:43 22:35
HongShenLu 23:45 22:32
QiShenLu 23:47 22:30
13 8 19
JinYunLu 22:11 22:54
JinShaJiangXiLu 22:13 22:51
FengZhuang 22:17 22:48
QiLianShanNanLu 22:20 22:46
ZhenBeiLu 22:22 22:43
DaDuHeLu 22:25 22:40
JinShaJiangLu 22:29 22:37
LongDeLu 22:31 22:34
WuNingLu 22:34 22:32
ZhangShouLu 22:36 22:30
JiangNingLu 22:38 22:28
HanZhongLu 22:41 22:25
ZiRanBoWuGuan 22:42 22:23
NanJingXiLu 22:45 22:21
HuaiHaiZhongLu 22:47 22:18
XinTianDi 22:50 22:15
MaDangLu 22:52 22:14
ShiBoHuiBoWuGuan 22:54 22:11
ShiBoDaDao 22:57 22:08
16 12 13
DiShuiHu 22:00 23:12
LinGangDaDao 22:03 23:09
ShuYuan 22:09 23:03
HuiNanDong 22:19 22:52
HuiNan 22:24 22:47
YeShengDongWuYuan 22:32 22:39
XinChang 22:39 22:32
HangTouDong 22:45 22:26
HeShaHangCheng 22:49 22:22
ZhouPuDong 22:55 22:16
LuoShanLu 23:02 22:09
HuaXiaZhongLuZhan 23:06 22:05
LongYangLuZhan 23:11 22:00
4
YanAnXiLu JinShaJiangLu 22:00
JiangSuLu YanAnXiLu 23:25
JinShaJiangLu JiangSuLu 23:59
JinShaJiangLu JiaoTongDaXue 18:00
Output
4
18
35
16

提示

第一个查询:在22:00,几乎所有地铁都没有停止运营。从延安西路到金沙江路一般可以选择3号线到4号线。注意到3号线向北方向的途径延安西路的末班车是22:44,又因为发车间隔是7分钟,所以22:02有一班。所以瑞比先生要等2分钟,加上开往金沙江路需要4分钟,共计用时6分钟。而如果选择4号线,会发现4号线开往宜山路方向在22:00有一班,所以不用等,加上4号线开往金沙江路同样需要4分钟,共计用时4分钟。所以答案为4。

第二个查询:在23:25的江苏路,等1分钟就能等到2号线的末班车。到达中山公园后,如果选择换乘,那么到达3/4号线的时间为23:32,此时3号线和4号线的所需方向都已经停止运营。所以瑞比先生选择步行。由于乘地铁从中山公园到延安西路所需的最短时间(不计换乘和等待)是2分钟,所以步行需要14分钟。所以答案为18。

第三个查询:在23:59,几乎所有的地铁都已经停止运行。如果选择金沙江路到隆德路到江苏路这条线路,需要花费 $(2+3)\times7=35$ 分钟。如果选择金沙江路到中山公园到江苏路这条线路,也需要花费 $(3+2)\times7=35$ 分钟时间。所以答案是35分钟。

第四个查询:在18:00,所有地铁都可以选择,可以选择3/4号线转10号线或13号线转11号线。

1 人解决,1 人已尝试。

1 份提交通过,共有 1 份提交。

8.9 EMB 奖励。

创建: 2 年,6 月前.

修改: 2 年,6 月前.

最后提交: 2 年,6 月前.

来源: 2017 CCCC 选拔

题目标签