好的，我们先根据前面的 C++ 标程（BFS 解法） 来整理一份详细的文字题解。

题意简述

我们有：

• 两个非负整数 $a, b$，初始时 $a$ 给定。
• 两种操作：
  1. $a \leftarrow a + 1$，成本 $x$。
  2. $a \leftarrow a \oplus 1$（异或 $1$，即翻转二进制最低位），成本 $y$。
• 目标：让 $a$ 变成 $b$，求最小成本；不可能则输出 $-1$。
• 数据范围：$1 \le a,b \le 100$，$1 \le x,y \le 10^7$，$t \le 10^4$ 个测试用例。

关键观察

1. 操作 $a \leftarrow a \oplus 1$ 只会改变 $a$ 的最低位：

   • 若 $a$ 是偶数（最低位 $0$），$a \oplus 1 = a+1$。
   • 若 $a$ 是奇数（最低位 $1$），$a \oplus 1 = a-1$。

2. 由于只能进行 $+1$ 和 $\oplus 1$，且 $a$ 可能先变大再变小（因为奇数时 $\oplus 1$ 会减少 $1$），因此最终答案的最优路径中，$a$ 的值不会超出 $b$ 太多，但理论上为了用 $\oplus 1$ 调整奇偶性，可能会先增加再减少。

3. 因为 $b \le 100$，并且奇数 $\oplus 1$ 会 $-1$，所以 $a$ 在最优过程中不会超过 $200$（证明略，但 BFS 开到 $200$ 足够安全）。

解法思路

这是一个最短路径问题，状态是当前的 $a$ 值，边有两种：

• $(val) \to (val+1)$，边权 $x$。
• $(val) \to (val \oplus 1)$，边权 $y$。

由于图很小（节点数最多 $201$），可以直接用 Dijkstra（边权非负）或 BFS 变种（因为边权不同，优先队列 Dijkstra 更安全）求从 $a$ 到 $b$ 的最短路。

算法步骤

1. 初始化距离数组 $dist[u] = \infty$，$dist[a] = 0$，小根堆 (cost, val)。
2. 当堆非空：
   • 弹出 (cost, val)，如果 $cost > dist[val]$ 则跳过。
   • 如果 $val = b$，可以提前结束（但继续也行）。
   • 尝试操作 $+1$：如果 $val+1 \le 200$ 且 $cost + x < dist[val+1]$，更新并入堆。
   • 尝试操作 $\oplus 1$：$nxt = val \oplus 1$，如果 $nxt \le 200$ 且 $cost + y < dist[nxt]$，更新并入堆。
3. 最终 $dist[b]$ 为最小成本，若仍为 $\infty$ 输出 $-1$。

为什么范围开到 $200$？

考虑最坏情况：$a = 100, b = 1$。
我们需要通过 $\oplus 1$ 让 $a$ 减小，但 $\oplus 1$ 只能发生在奇数 → 偶数（减 $1$）。
为了制造奇数，可能需要先 $+1$ 若干次，所以 $a$ 会暂时超过 $100$。
但一旦超过 $200$ 再回来不会更优（可以通过分析证明），因为 $x, y \ge 1$。

时间复杂度

• 每个测试用例 BFS/Dijkstra 访问最多 $200$ 个节点。
• 边数 $O(n)$，堆操作 $O(n \log n)$。
• 总复杂度 $O(t \cdot 200 \log 200)$，完全可行。

样例验证

以样例 1 4 1 2 为例：

• 初始 $a=1$。
• 路径：$1 \xrightarrow{+1} 2 \xrightarrow{+1} 3 \xrightarrow{+1} 4$，成本 $3$。
• BFS 也会找到同样的结果。

正确性说明

• 因为所有边权为正，Dijkstra 保证第一次弹出 $b$ 时就是最小成本。
• 范围 $200$ 足够包含最优路径上的所有中间值（可严格证明：若超过 $200$，则必能换成更优路径）。

这样，我们就得到了一个正确、高效、易于实现的解法。