CF1659C Line Empire

你是一位雄心勃勃的国王，想要成为“实数之皇”。但在此之前，你必须先成为“整数之皇”。 考虑一条数轴。你的帝国首都最初位于 $0$。有 $n$ 个未被征服的王国，分别位于 $0 < x_1 < x_2 < \ldots < x_n$ 的位置。你想要征服所有其他王国。 你有两种可用的行动： - 你可以将首都的位置（假设当前位置为 $c_1$）迁移到任意一个已被征服的王国（其位置为 $c_2$），花费为 $a\cdot |c_1-c_2|$。 - 你可以从当前首都（位置为 $c_1$）出发，征服一个未被征服的王国（其位置为 $c_2$），花费为 $b\cdot |c_1-c_2|$。如果在目标和你的首都之间有未被征服的王国，则不能征服该王国。 注意，你不能将首都迁移到没有王国的位置。换句话说，任何时候你的首都只能位于 $0$ 或 $x_1,x_2,\ldots,x_n$ 之一。还要注意，征服一个王国不会改变首都的位置。 请你求出征服所有王国的最小总花费。最终首都可以位于任意位置。

第一行包含一个整数 $t$（$1 \le t \le 1000$），表示测试用例的数量。每个测试用例的描述如下。 每个测试用例的第一行包含三个整数 $n$、$a$ 和 $b$（$1 \leq n \leq 2 \cdot 10^5$；$1 \leq a,b \leq 10^5$）。 每个测试用例的第二行包含 $n$ 个整数 $x_1, x_2, \ldots, x_n$（$1 \leq x_1 < x_2 < \ldots < x_n \leq 10^8$）。 所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。

对于每个测试用例，输出一个整数，表示征服所有王国的最小花费。

以下是第二个测试用例的最优操作序列： 1. 以花费 $3\cdot(1-0)=3$ 征服位于 $1$ 的王国。 2. 以花费 $6\cdot(1-0)=6$ 将首都迁移到 $1$。 3. 以花费 $3\cdot(5-1)=12$ 征服位于 $5$ 的王国。 4. 以花费 $6\cdot(5-1)=24$ 将首都迁移到 $5$。 5. 以花费 $3\cdot(6-5)=3$ 征服位于 $6$ 的王国。 6. 以花费 $3\cdot(21-5)=48$ 征服位于 $21$ 的王国。 7. 以花费 $3\cdot(30-5)=75$ 征服位于 $30$ 的王国。 总花费为 $3+6+12+24+3+48+75=171$。你无法得到比这更低的花费。 由 ChatGPT 4.1 翻译