题解：P14079 [GESP202509 八级] 最短距离

a_gold_TomAndJerry · 2025-10-02 00:02:37 · 题解

题意：对于一个有 N=10^{18} 的带全无向图，规定其中两个互质的节点所连的边权值为 p，否则为 q，求节点 a_i 到 b_i 的最短权值和。

一眼看到以为是Floyd板子，然后读了发现只是个简单的数学题。

设最小路径长度为 d。

考虑2种情况：a_i 和 b_i 互质或不互质。每种情况中又分为三种小情况：直接连边，过节点1（两条互质路径和）和过最小公倍数节点（两条不互质路径和）。

对于第1种：当直接连边时，d=p；过节点1时，d=2p；过最小公倍数节点时，d=2q。综上，当 a_i 和 b_i 互质时，d=\min(p,2q)。

对于第2种：当直接连边时，d=q；过节点1时，d=2p；过最小公倍数节点时，d=2q。综上，当 a_i 和 b_i 互质时，d=\min(q,2p)。

特殊地，当 p=1 或 q=1 时，d=p；当 p=q 时，d=0。

然后分类讨论即可。

AC Code：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,p,q;
int main(){
    scanf("%lld%lld%lld",&n,&p,&q);
    for(int i=1;i<=n;++i){
        ll a,b;
        scanf("%lld%lld",&a,&b);
        if(a==b){
            cout<<0<<'\n';
            continue;
        }  
        if(a==1||b==1){
            cout<<p<<'\n';
            continue;
        }
        if(__gcd(a,b)==1){
            cout<<min(2*q,p)<<'\n';
            continue;   
        }
        cout<<min(2*p,q)<<'\n'; 
    }
    return 0;
}