1 人解决,2 人已尝试。
1 份提交通过,共有 5 份提交。
9.8 EMB 奖励。
单点时限: 8.0 sec
内存限制: 256 MB
上海地铁的末班车早得世界闻名。
作为码农,瑞比先生经常加班,经常要赶末班车。他现在希望你帮忙计算一下回家需要多少时间,免得 Mrs. Bunny 担心。
有关上海地铁的操作规则,我想大家都已经很熟悉了。这里有几点再要说明一下:
第一行一个整数,表示地铁线路数。
对于每一条线路,首先是三个整数,分别为线路编号、发车间隔和经停站数,然后接下来每一行分别是站名、正向经过的末班车时间、反向经过的末班车时间。
然后是一行一个整数,表示查询数目 $Q$ $(1 \leq Q \leq 300)$。每次查询提供出发站名,目的地站名,和出发时间 (HH:MM)
。出发时间晚于 12:00,早于 24:00。
对于每个询问,输出一行:最少需要的时间(单位:分钟)。
输入保证有解。
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
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 人解决,2 人已尝试。
1 份提交通过,共有 5 份提交。
9.8 EMB 奖励。