#P11791. [JOI 2017 Final] 准高速电车 / Semiexpress
[JOI 2017 Final] 准高速电车 / Semiexpress
题目描述
JOI 铁路公司是 JOI 国唯一的铁路公司。
在某条铁路沿线共有 个站点,依次编号为 。当前有两种列车服役,分别是高速列车和普通列车。
-
普通列车每站都停,对于每一个 ,从站点 到站点 用时 分钟。
-
高速列车只在站点 停车,对于每一个 ,从站点 到站点 用时 分钟。
JOI 铁路公司拟定开设第三类车次:准高速列车。对于每一个 ,从站点 到站点 用时 分钟。准高速列车停的站点还没有决定好,但是这些站点必须满足以下要求:
-
高速列车停的所有站点准高速列车都必须停。
-
准高速列车必须停恰好 个站点。
JOI 铁路公司想要最大化从 号站点在 分钟内可以到的站点数目(不计 号站点,不计等车和换乘时间),JOI 铁路公司想要合理地安排站点使得这个数目最大。
当合理地安排准高速列车停的站点时,从 号站点出发在 分钟内抵达的站点( 号站点不计)最多是多少?
输入格式
第一行三个整数 ,意义如题面所示。
第二行三个整数 ,意义如题面所示。
第三行一个整数 ,意义如题面所示。
接下来 行,这 行中的第 行有一个整数 ,表示快车停的站点。
输出格式
一行一个整数,表示答案。
10 3 5
10 3 5
30
1
6
10
8
10 3 5
10 3 5
25
1
6
10
7
90 10 12
100000 1000 10000
10000
1
10
20
30
40
50
60
70
80
90
2
12 3 4
10 1 2
30
1
11
12
6
300 8 16
345678901 123456789 234567890
12345678901
1
10
77
82
137
210
297
300
72
1000000000 2 3000
1000000000 1 2
1000000000
1
1000000000
3000
提示
【样例解释】
对于样例 ,一共有 个站点,快车停 三个站点。我们假设准快车停 五个站点,于是,在 中,我们可以从 号站点在 分钟内抵达除了 号站点的所有站点。
对于某些 ,从 号站点到 号站点最优的方案如下:
-
从 号站点到 号站点,只需要乘坐普通列车,时间为 分钟。
-
从 号站点到 号站点,先乘坐高速列车到站点 ,然后转乘普通列车,时间为 分钟。
-
从 号站点到 号站点,先乘坐高速列车到站点 ,然后转乘准高速列车,时间为 分钟。
-
从 号站点到 号站点,先乘坐高速列车到站点 ,然后转乘准高速列车到站点 ,再换乘普通列车,时间为 分钟。
【数据范围与约定】
所有的数据满足以下条件:
-
。
-
。
-
。
-
Subtask ( pts):。
-
Subtask ( pts):。
-
Subtask ( pts):无特殊限制。