A23832. 最短距离
填空题
困难
知识点
题目描述
最短距离
题目描述
给定正整数p,q以及常数N=1018 。现在构建一张包含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）组询问给定两个正整数ai,bi ，你需要回答结点ai与结点bi之间的最短距离。
输入格式
第一行，三个正整数n,p,q ，分别表示询问数量，结点编号互质时的边权，以及结点编号不互质时的边权。
接下来 n行，每行两个正整数ai,bi ，表示一组询问。
输出格式
输出共n 行，每行一个整数，表示结点 ai与结点bi 之间的最短距离。
样例
输入样例 1
4 4 3
1 2
2 3
4 2
3 5输出样例 1
4
4
3
4输入样例 2
5 2 6
1 2
2 3
4 2
3 5
6 6
输出样例 2
2
2
4
2
0
数据范围
对于 % 的测试点，保证 1≤n≤10，1≤ai,bi≤50 。
对于另外 30% 的测试点，保证1≤ai,bi≤250 。
对于所有测试点，保证1≤n≤104 ，1≤ai,bi≤109 ，1≤p,q≤109 。
参考答案
#include <algorithm>
#include <cstdio>
using namespace std;
const int N = 1e5 + 5;
int n, p, q;
int a, b;
int ans;
int gcd(int a, int b) {
if (!a || !b) return a + b;
return gcd(b, a % b);
}
int main() {
scanf("%d%d%d", &n, &p, &q);
while (n--) {
scanf("%d%d", &a, &b);
if (a == b)
ans = 0;
else if (a == 1 || b == 1)
ans = p;
else {
ans = min(p + p, q + q);
if (gcd(a, b) == 1)
ans = min(ans, p);
else
ans = min(ans, q);
}
printf("%d\n", ans);
}
return 0;
}
上一题
下一题