logo AlgoBeat OnlineJudge
登录 注册

#104053. [BZOJ 4053] [Cerc2013]Subway

内存限制：256 MiB 时间限制：20000 ms 标准输入输出
题目类型：传统 评测方式：文本比较
上传者： 匿名
提交 提交记录 统计 测试数据 讨论 题解

题目描述

小 J 要坐地铁到小 M 家去玩。

有很多的地铁站，有很多条双向的地铁线路连接它们。

从一个站到一个直接相邻的站都只要 分钟，换线不需要时间。

给你地铁图，你的任务是帮助小 J 安排他的路线，使得换乘（在一条线路上回头也算换乘）次数尽量少，且让他坐的尽量久。

输入格式

第一行一个整数 ，代表数据组数。

每一组测试数据如下:

每组数据用一个回车开头，接下来的两行以 Stops: 和 Lines: (不包含引号)开头，并且分别包含站点和线路的名称，之间用一个逗号和一个空格隔开。

接下来对于每条线路有单独的一行，以线路的名称加 route 开头，后面包含它经过的站点，之间用一个逗号和一个空格隔开。

最后两行告诉你小 J 与小 M 的位置。

输出格式

对于每组测试数据，打印单独的一行代表小 J的最优线路（详情请见样例数据），保证最优路径存在。

样例

样例输入 #1

Stops: OxfordCircus, PiccadillyCircus, HydeParkCorner, King’sCross, GreenPark, Arsenal, Victoria, Highbury&Islington, LeicesterSquare
Lines: Blue, Cyan
Cyan route: Highbury&Islington, King’sCross, OxfordCircus, GreenPark, Victoria
Blue route: HydeParkCorner, GreenPark, PiccadillyCircus, LeicesterSquare, King’sCross, Arsenal
Johny lives at King’sCross
Michelle lives at GreenPark
Stops: OxfordCircus, PiccadillyCircus, HydeParkCorner, King’sCross, GreenPark, Arsenal, Victoria, Highbury&Islington, LeicesterSquare
Lines: Blue, Cyan
Cyan route: Highbury&Islington, King’sCross, OxfordCircus, GreenPark, Victoria
Blue route: HydeParkCorner, GreenPark, PiccadillyCircus, LeicesterSquare, King’sCross, Arsenal
Johny lives at PiccadillyCircus
Michelle lives at LeicesterSquare
Stops: OxfordCircus, PiccadillyCircus, HydeParkCorner, King’sCross, GreenPark, Arsenal, Victoria, Highbury&Islington, LeicesterSquare
Lines: Blue, Cyan
Cyan route: Highbury&Islington, King’sCross, OxfordCircus, GreenPark, Victoria
Blue route: HydeParkCorner, GreenPark, PiccadillyCircus, LeicesterSquare, King’sCross, Arsenal
Johny lives at Victoria
Michelle lives at HydeParkCorner

样例输出 #1

optimal travel from King’sCross to GreenPark: 1 line, 3 minutes
optimal travel from PiccadillyCircus to LeicesterSquare: 1 line, 1 minute
optimal travel from Victoria to HydeParkCorner: 2 lines, 7 minutes

数据范围与提示

对于 的数据， 站点数 ， 线路总长度 ， 名称长度 ，名称可以包括字母，数字，减号，单引号和按位与符号，保证图中没有自环。

显示分类标签

编辑器加载中 …
Powered by SYZOJ. Modified by Zemu (UnratedCheater).
项目源码 · 陶片放逐 · 新ICP备2026003452号-2
当前版本：V1.7.2-premium