CF1491B Minimal Cost

给你一个 $n$ 行 $10^6+2$ 列的图，行从 $1$ 到 $n$ 标号，列从 $0$ 到 $10^6+1$ 标号。 为简便，下面用 $(i,j)$ 表示第 $i$ 行第 $j$ 列的节点。 一开始每一行 $i$ 都恰好有一个障碍物 $(i,a_i)$。你可以将障碍物移动到四周空的节点（不能移出图的范围），上下移动一个单位花费 $u$，左右移动一个单位花费 $v$。（可参照上图） 你需要使得 $(1,0)$ 到 $(n,10^6+1)$ 之间有一条路径（只能上下左右移动，不能越过障碍物），求移动障碍物的最小花费。

第一行为数据组数 $t$ ($1 \leq t \leq 10^4$)。 每组数据第一行为三个整数 $n,u,v$ ($2 \leq n \leq 100, 1 \leq u,v \leq 10^9$) —— 图的行数、上下移动一个单位的花费、左右移动一个单位的花费 每组数据第二行为 $n$ 个整数 $a_1,a_2,...,a_n$ ($1 \leq a_i \leq 10^6$) —— $a_i$ 表示第 $i$ 行有障碍物 $(i,a_i)$。 保证 $\sum n \leq 2 \cdot 10^4$

对于每组数据，输出一个整数 —— 移动障碍物的最小花费。 显然在题目限制下，必然有解。

In the first sample, two obstacles are at $ (1, 2) $ and $ (2,2) $ . You can move the obstacle on $ (2, 2) $ to $ (2, 3) $ , then to $ (1, 3) $ . The total cost is $ u+v = 7 $ coins. In the second sample, two obstacles are at $ (1, 3) $ and $ (2,2) $ . You can move the obstacle on $ (1, 3) $ to $ (2, 3) $ . The cost is $ u = 3 $ coins.