A67214 | 最短距离

试题名称：最短距离

时间限制： 1.0 s

内存限制：512.0 MB

3.1.1     题目描述

给定正整数p, q 以及常数N = 10⁸ 。现在构建一张包含 N 个结点的带权⽆向图 ，结点依次以 1 , 2, .... , N 编号 。对于 任意满⾜ 1 ≤ u < v ≤ N 的 u, v ， 向图中加⼊一条连接结点 u 与结点 v 的⽆向边 ，边权取决于 u, v 是否互质：

  若 u, v 互质（即 u, v 的最⼤公因数为 1） ，则连接结点 u 与结点 v 的⽆向边长度为 p；

  否则连接结点 u 与结点 v 的⽆向边长度为 q。

现在给定 n 组询问 ，第 i（ 1 ≤ i ≤ n） 组询问给定两个正整数a_i , b_i ，你需要回答结点 a_i 与结点 b_i 之间的最短距离。

3.1.2     输入格式

第一⾏ ，三个正整数 n, p, q ，分别表⽰询问数量 ，结点编号互质时的边权 ，以及结点编号不互质时的边权。

接下来 n ⾏ ，每⾏两个正整数 a_i , b_i ，表⽰一组询问。

3.1.3     输出格式

输出共 n ⾏ ，每⾏一个整数 ，表⽰结点 a_i 与结点 b_i 之间的最短距离。

3.1.4     样例

3.1.4.1     输入样例 1

4 4 3

1 2

2 3

4 2

3 5

3.1.4.2     输出样例 1

4

4

3

4

3.1.4.3     输入样例 2

6 5  2  6

1  2

2  3

4  2

3  5

6  6

3.1.4.4 输出样例 2

2

2

4

2

0

3.1.5     数据范围

对于 30% 的测试点 ，保证 1  ≤ n ≤ 10 ， 1≤ a_i , b_i ≤ 50。

对于另外 30% 的测试点 ，保证 1 ≤ a_i , b_i  ≤ 250。

对于所有测试点 ，保证 1 ≤ n ≤ 104 ，1  ≤ a_i , b_i  ≤ 10⁹ ，1 ≤ p, q ≤ 10⁹ 。