专栏文章

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

aa_gold_TomAndJerry
P14079题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minqepfr
此快照首次捕获于
2025/12/02 06:39
3 个月前
此快照最后确认于
2025/12/02 06:39
3 个月前
查看原文
题意：对于一个有 N=1018N=10^{18} 的带全无向图，规定其中两个互质的节点所连的边权值为 pp，否则为 qq，求节点 aia_i 到 bib_i 的最短权值和。
一眼看到以为是Floyd板子，然后读了发现只是个简单的数学题。
设最小路径长度为 dd。
考虑2种情况：aia_i 和 bib_i 互质或不互质。每种情况中又分为三种小情况：直接连边，过节点1（两条互质路径和）和过最小公倍数节点（两条不互质路径和）。
对于第1种：当直接连边时，d=pd=p；过节点1时，d=2pd=2p；过最小公倍数节点时，d=2qd=2q。综上，当 aia_i 和 bib_i 互质时，d=min⁡(p,2q)d=\min(p,2q)。
对于第2种：当直接连边时，d=qd=q；过节点1时，d=2pd=2p；过最小公倍数节点时，d=2qd=2q。综上，当 aia_i 和 bib_i 互质时，d=min⁡(q,2p)d=\min(q,2p)。
特殊地，当 p=1p=1 或 q=1q=1 时，d=pd=p；当 p=qp=q 时，d=0d=0。
然后分类讨论即可。

AC Code：

CPP
#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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...