《P14079 [GESP202509 八级] 最短距离》

题目背景对应的选择、判断题试题 - GESP 202509 C 八级 - 洛谷有题题目描述给定正整数 p,q 以及常数 N1018。现在构建一张包含 N 个结点的带权无向图结点依次以 1,2,…,N 编号。对于任意满足 1≤uv≤N 的 u,v向图中加入一条连接结点 u 与结点 v 的无向边边权取决于 u,v 是否互质若 u,v 互质即 u,v 的最大公因数为 1则连接结点 u 与结点 v 的无向边长度为 p否则连接结点 u 与结点 v 的无向边长度为 q。现在给定 n 组询问第 i1≤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说明/提示对于 30% 的测试点保证 1≤n≤101≤ai​,bi​≤50。对于另外 30% 的测试点保证 1≤ai​,bi​≤250。对于所有测试点保证 1≤n≤1041≤ai​,bi​≤1091≤p,q≤109。代码实现#include iostream #include algorithm using namespace std; typedef long long ll; ll gcd(ll a, ll b) { while(b ! 0) { ll rem a % b; a b; b rem; } return a; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; ll p, q; cin n p q; while(n--) { ll a,b; cin a b; if(a b) { cout 0\n; } else if(min(a,b) 1) { cout p \n; } else { ll g gcd(a,b); if(g 1) { cout min(p, 2*q) \n; } else { cout min(q, 2*p) \n; } } } return 0; }