← 返回题目列表

Codeforces · 1491/B

B. 最低成本

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

有一个包含 $$$n$$$ 行和 $$$10^6 + 2$$$ 列的图表,其中行编号从 $$$1$$$ 到 $$$n$$$,列编号从 $$$0$$$ 到 $$$10^6 + 1$$$:

让我们用 $$$(i, j)$$$ 表示 $$$i$$$ 行和 $$$j$$$ 列中的节点。

最初,对于每个 $$$i$$$,第 $$$i$$$ 行只有一个障碍物 - 在节点 $$$(i, a_i)$$$ 处。您想要移动一些障碍物,以便通过移动该图的边(无法穿过障碍物)从节点 $$$(1, 0)$$$ 到达节点 $$$(n, 10^6+1)$$$。将一个障碍物移动到相邻的无边节点需要花费 $$$u$$$ 或 $$$v$$$ 硬币,如下所示:

- 如果节点$$$(i, j)$$$中有障碍物,您可以使用$$$u$$$硬币将其移动到$$$(i-1, j)$$$或$$$(i+1, j)$$$,如果该节点存在并且当前该节点没有障碍物。
- 如果节点$$$(i, j)$$$中有障碍物,您可以使用$$$v$$$硬币将其移动到$$$(i, j-1)$$$或$$$(i, j+1)$$$,如果该节点存在且当前该节点没有障碍物。
- 请注意,您无法将障碍物移动到网格之外。例如,您无法将障碍物从 $$$(1,1)$$$ 移动到 $$$(0,1)$$$。

请参阅上图以更好地理解。

现在您需要计算从节点 $$$(1, 0)$$$ 穿过该图的边缘而不穿过障碍物到达节点 $$$(n, 10^6+1)$$$ 所需花费的最少硬币数量。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。

每个测试用例的第一行包含三个整数 $$$n$$$、$$$u$$$ 和 $$$v$$$ ($$$2 \le n \le 100$$$, $$$1 \le u, v \le 10^9$$$)——图中的行数以及分别垂直和水平移动所需的硬币数量。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^6$$$) — 其中 $$$a_i$$$ 表示第 $$$i$$$ 行中的障碍物位于节点 $$$(i, a_i)$$$ 中。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^4$$$。

输出

对于每个测试用例,输出一个整数 - 从节点 $$$(1, 0)$$$ 穿过该图的边缘而不穿过障碍物到达节点 $$$(n, 10^6+1)$$$ 所需花费的最少硬币数量。

可以证明,在问题的约束下,总有一种方法可以使这样的旅行成为可能。

示例

输入 #1

3
2 3 4
2 2
2 3 4
3 2
2 4 3
3 2

输出 #1

7
3
3

注意

在第一个示例中,两个障碍物位于 $$$(1, 2)$$$ 和 $$$(2,2)$$$ 处。您可以将 $$$(2, 2)$$$ 上的障碍物移动到 $$$(2, 3)$$$,然后移动到 $$$(1, 3)$$$。总成本为 $$$u+v = 7$$$ 硬币。

在第二个示例中,两个障碍物位于 $$$(1, 3)$$$ 和 $$$(2,2)$$$ 处。您可以将$$$(1, 3)$$$上的障碍物移至$$$(2, 3)$$$。成本为 $$$u = 3$$$ 硬币。