← 返回题目列表

Codeforces · 1346/I

I. 吃豆人 2.0

中文机器翻译题面 查看原题

Polycarp 正在开发旧视频游戏“吃豆人”的新版本。虽然他真的很喜欢玩原来的游戏,但他不喜欢它的某些方面,所以他决定稍微改变一下规则。

在Polycarp的版本中,你扮演吃豆人,你必须收集散布在游戏世界中的颗粒,同时避开危险的幽灵(与原版没有区别)。 Polycarp 不喜欢原作中无法逃脱幽灵的事实,因此,在他的版本中,游戏世界被划分为 $$$n$$$ 个安全区域,它们之间有 $$$m$$$ 单向路径 — 并且保证吃豆人可以从任何其他安全区域到达任何安全区域。由于安全区是安全的,当吃豆人在那里时,鬼魂无法攻击它,只有在穿过路径时它才会处于危险之中。吃豆人在安全区 $$$s$$$ 开始游戏。

所有颗粒都散布在安全区域;最初,第 $$$i$$$ 个安全区域包含 $$$a_i$$$ 颗粒(如果吃豆人位于安全区域,它可以自由收集其中的所有颗粒)。收集到的弹丸会消失,但收集到游戏世界中的最后一个弹丸后,新的弹丸会在安全区域中生成,数量与之前相同($$$a_i$$$ 新弹丸会在第 $$$i$$$ 区域中生成)。颗粒可以重生任意次数,因此游戏本质上是无限的。

波利卡普已经确定了游戏世界的结构以及每个安全区的弹丸数量。现在他正在尝试看看这个游戏是否足够困难。游戏中有 $$$q$$$ 个目标,第 $$$i$$$ 个目标是从游戏开始时收集至少 $$$C_i$$$ 颗粒。 Polycarp 将第 $$$i$$$ 个目标的难度表示为玩家必须穿过单向路径才能收集 $$$C_i$$$ 颗粒的最少次数(因为仅穿过一条路径就会使吃豆人陷入危险)。如果在吃豆人收集颗粒时某条路径被多次遍历,则它会以相同的次数包含在答案中。

帮助Polycarp计算每个目标的难度!

输入

第一行包含四个整数 $$$n$$$、$$$m$$$、$$$q$$$ 和 $$$s$$$ ($$$2 \le n \le 15$$$; $$$n \le m \le n(n-1)$$$; $$$1 \le q \le 5000$$$; $$$1 \le s \le n$$$) — 分别是安全区的数量、路径的数量、目标的数量和起始安全区的索引。

第二行包含 $$$n$$$ 整数 $$$a_1$$$, $$$a_2$$$, ..., $$$a_n$$$ ($$$1 \le a_i \le 10^9$$$),其中 $$$a_i$$$ 是第 $$$i$$$ 个安全区域中的初始颗粒数(以及在当收集到世界上最后一个颗粒时,第 $$$i$$$ 个安全区)。

接下来是 $$$m$$$ 行,每行包含两个整数 $$$v_i$$$ 和 $$$u_i$$$ ($$$1 \le v_i, u_i \le n$$$; $$$v_i \ne u_i$$$) 表示从安全区 $$$v_i$$$ 到安全区的单向路径$$$u_i$$$。每个有序对 $$$(v_i, u_i)$$$ 在该部分中最多出现一次(从 $$$v_i$$$ 到 $$$u_i$$$ 没有多条路径),并且可以使用这些路径从每个其他安全区到达每个安全区。

最后一行包含 $$$q$$$ 整数 $$$C_1$$$, $$$C_2$$$, ..., $$$C_q$$$ ($$$1 \le C_i \le 10^{15}$$$),其中 $$$C_i$$$ 是玩家为了满足第 $$$i$$$ 任务必须收集的最小颗粒数目标。

输出

对于每个目标 $$$i$$$,打印一个整数 - 它的难度(玩家必须沿着某条路径穿越的最少次数才能收集至少 $$$C_i$$$ 颗粒)。

示例

输入 #1

3 4 2 1
3 1 2
1 2
2 1
1 3
3 1
5 8

输出 #1

1
3

输入 #2

5 7 4 2
1 3 2 2 1
2 3
4 2
3 4
3 1
1 4
5 4
4 5
7 14 23 27

输出 #2

2
6
10
13

输入 #3

4 4 3 3
2 3 1 4
3 4
4 1
1 2
2 3
13 42 1337

输出 #3

3
13
401

注意

考虑第一个测试。为了收集$$$5$$$颗粒,玩家应该在安全区$$$1$$$(正在开始)收集$$$3$$$颗粒,移动到$$$3$$$区域,在那里收集$$$2$$$颗粒。

为了收集$$$8$$$颗粒,玩家应该在安全区$$$1$$$收集$$$3$$$颗粒,前往$$$2$$$,收集$$$1$$$颗粒,前往$$$1$$$没有获得颗粒,前往$$$3$$$,收集$$$2$$$颗粒。现在世界上最后一个颗粒已收集完毕,因此它们会重生。玩家可以在安全区$$$3$$$收集$$$2$$$颗粒,现在收集的颗粒数量为$$$8$$$。

考虑第二个测试。

为了收集 $$$7$$$ 颗粒,我们执行以下操作:$$$2(+3) \rightarrow 3(+2) \rightarrow 4(+2)$$$。以这种方式收集了 $$$7$$$ 颗粒。

为了收集 $$$14$$$ 颗粒,我们执行以下操作: $$$2(+3) \rightarrow 3(+2) \rightarrow 1(+1) \rightarrow 4(+2) \rightarrow 5(+1)$$$ 颗粒重生 $$$5(+1) \rightarrow 4 (+2) \rightarrow 2(+3)$$$。以这种方式收集了$$$15$$$颗粒。

为了收集 $$$23$$$ 颗粒,我们执行以下操作: $$$2(+3) \rightarrow 3(+2) \rightarrow 1(+1) \rightarrow 4(+2) \rightarrow 5(+1)$$$ 颗粒重生 $$$5(+1) \rightarrow 4(+2) \rightarrow 2(+3) \rightarrow 3(+2) \rightarrow 1(+1)$$$ 颗粒重生 $$$1(+1) \rightarrow 4(+2) \rightarrow 2(+3)$$$。以这种方式收集了$$$24$$$颗粒。