#P4489. [Jsoi2015]地铁线路

    ID: 3723 传统题 1500ms 512MiB 尝试: 177 已通过: 38 难度: 7 上传者: 标签>难度分类提高+/省选-图论辅助点压缩边枚举与搜索广度优先搜索动态规划DAG 动态规划排序与序列处理前后缀最值构造与建模绝对值分段线性化CF2300

[Jsoi2015]地铁线路

[JSOI2015] 地铁线路

题目描述

地铁网有 NN 条线路和 SS 个车站。每条线路由按顺序排列的停靠站组成,列车可以从任一端向另一端运行。一条线路上同一个站可以出现多次。可以在同一车站下车后重新上车,换乘另一条线路或换乘原线路反方向的列车。

每次上车支付 11 元,包括第一次乘车以及之后的每次换乘。同一趟列车每驶过相邻的两个停靠位置,用时 11 分钟。停站和换乘不耗时。

JYY 想从 AA 站到 BB 站。请先求最少车费,再在车费最少的行程中求最长乘车时间。

输入格式

第一行输入两个正整数 N,SN,S。

第二行输入 SS 个站名,各不相同。站名长不超过 4040,仅包含英文字母、数字和连字符 -。

接下来 NN 行各描述一条线路。第 ii 行先输入正整数 LiL_i,再依次输入 LiL_i 个停靠站的站名。

最后一行输入两个不同的站名 A,BA,B。

输出格式

第一行输出最少车费,第二行输出在该车费下的最长乘车时间。

若无法到达,第一行输出 -1,第二行输出 0。

样例

2 5
A B C D E
4 A B C D
3 C D E
A D
1
3

数据范围

2≤N≤4×1052\le N\le 4\times10^5,S≤3×105S\le3\times10^5,∑i=1NLi≤8×105\sum_{i=1}^N L_i\le8\times10^5。