专栏文章

题解：AT_abc232_g [ABC232G] Modulo Shortest Path

SSTDLRZ
AT_abc232_g题解参与者 2已保存评论 1

文章操作

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

当前评论
1 条
当前快照
1 份
快照标识符
@miq8ocd8
此快照首次捕获于
2025/12/04 00:46
3 个月前
此快照最后确认于
2025/12/04 00:46
3 个月前
查看原文
思路来自于 @0x3b800001 的（稍改），但是我希望我能用更清晰的语言让大家理解。
这篇比较偏向萌新。因为作者也是萌新呀！

暴力

直接暴力建边，然后跑一遍最短路即可。

正解

观察一条边的边权：u→vu \to v 的边权为 (au+bv) mod m(a_u+b_v) \bmod m。
发现有取模操作，先考虑没有取模操作的特殊情况。
即：u→vu \to v 的边权为 (au+bv)(a_u+b_v)。
我们该如何建边？我们可以枚举 uu，一旦 uu 固定，那么不管你的 vv 是什么，aua_u 就已经固定了。
此时，我们可以建立一个大节点 TT，这个节点是 1∼n1 \sim n 的中转节点。
我们可以让 uu 节点先用 aua_u 的边权连向 TT，然后让 TT 连向这些小节点 vv，边权为 bvb_v。这样拆分，就不用 O(n2)\mathcal O(n^2) 的建图啦。
接着，再跑一遍 dijkstra，就可以结束了。
再考虑回一般情况。
我们还是一样，枚举 uu，那么 aua_u 就固定了，就只剩下 bvb_v 的事情了。
大家应该都知道，这个取模有两种情况：
  • au+bv<ma_u+b_v<m：值为 au+bva_u+b_v，是我们考虑的特殊情况。
  • au+bv≥ma_u+b_v \ge m：值为 au+bv−ma_u+b_v-m。
因为 aua_u 固定，如果我们将节点以 bb 为关键字从小到大排序，那么肯定有：前一半部分是第一种情况，后一半部分是第二种情况。
于是我们就以 bb 为关键字从小到大将节点排序。
此时，只使用节点 TT 来进行连边就不够了。我们可以来一个前后缀节点，定义：
  • 对于前缀节点 i+ni+n，表示的节点是 1∼i1 \sim i 这个整体。
  • 对于后缀节点 i+2ni+2n，表示的节点是 i∼ni \sim n 这个整体。
模仿特殊情况的连边方式，稍微改一改。
因为对于两个前缀节点 u+n,v+n(u<v)u+n,v+n(u<v)，v+nv+n 节点是覆盖 u+nu+n 节点的整体的。
所以，我们可以让 i+n→i+n−1(i>1)i+n \to i+n-1(i>1)，如果大的节点行那小的节点也行，边权为 00；
同理，我们也可以让 i+2n→i+1+2n(i<n)i+2n \to i+1+2n(i<n)，边权为 00。
对于一个节点 ii，设 1∼ans−11 \sim ans-1 的节点是特殊情况，ans∼nans \sim n 的节点需要在特殊情况的基础下再减去 mm。也就是说，1∼ans−11 \sim ans-1 的边权是 aua_u，ans∼nans \sim n 的边权是 au−ma_u-m。
至于从整体节点连到单个节点，不管是 ii 的前缀节点 i+ni+n，还是 ii 的后缀节点 i+2ni+2n，我们都令他的边权为 bib_i。
正确性：像我们之前说的，对于两个前缀节点 u+n,v+n(u<v)u+n,v+n(u<v)，v+nv+n 节点是覆盖 u+nu+n 的整体的。假设我们现在需要到 uu 节点，于是我们可以从 v+nv+n 一直走到 u+nu+n，然后再走到 uu。所以是正确的。
总结（上图，一图胜千言）：
这个图只是举个例子，因为淡绿色的边不能污染了其他颜色的边，所以这里只举了部分连边例子。
但是我们发现：边权可能为负！
考虑怎么让边权变为自然数。我们发现，只有当单个节点连向后缀节点的时候，才会产生负数的边。
于是，我们考虑将 bib_i 也一同加入。也就是说，我们的单个节点 ii 连向的整体节点 ans∼nans \sim n 的边权变成了 bans+ai−mb_{ans}+a_i-m，此时这个边权确实非负了。但是？如果后缀节点之间节点的连边边权还是 00 的话，就有问题。所以我们要调整一下这些边权。
于是，我们走一条边 u+2n→u+1+2nu+2n \to u+1+2n，因为我们当前 bb 的贡献是 bu+2nb_{u+2n}，现在要变成 bu+1+2nb_{u+1+2n}，于是我们令这条边权为 bu+1+2n−bu+2nb_{u+1+2n}-b_{u+2n}。
这样，我们的 i+2n→ii+2n \to i 边的边权就不再需要考虑到 bb 的贡献，直接赋值为 00 即可。
诶？等等？bb 数组是从小到大排序的？那这个边权不也是非负的嘛？
这不就完美解决了嘛？
上图（不再展示单个节点连向前缀节点的边）：
其中，红色的边强调该边权有更改。
代码（应该有可读性吧）：
CPP
#include<bits/stdc++.h>
#define x0 x_0
#define x1 x_1
#define y0 y_0
#define y1 y_1
#define yn y_n
#define j0 j_0
#define j1 j_1
#define k0 k_0
#define k1 k_1
#define d0 d_0
#define d1 d_1
#define LL long long
#define LD long double
#define ZPB push_back
#define ZPF push_front
#define US unsigned
using namespace std;
struct node{
	int a,b,id;
	bool operator < (const node &o)const{return (b!=o.b ? b<o.b : id<o.id);}
};
struct Enode{
	int v;
	LL w;
	bool operator < (const Enode &o)const{return w>o.w;}
};
/*
[1,n]: real_node
[n+1,2n]: qjh_node
[2n+1,3n]: hjh_node
*/
node val[200010];
int n,m,st,ed;
const LL LLmex=1e18;
LL dp[600010];
vector<Enode> G[600010];
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;++i) cin>>val[i].a,val[i].id=i;
	for(int i=1;i<=n;++i) cin>>val[i].b;
	sort(val+1,val+n+1);
	for(int i=1;i<=n;++i){
		if(val[i].id==1) st=i;
		if(val[i].id==n) ed=i;
		G[n+i].ZPB({i,val[i].b}),
		G[(n<<1)+i].ZPB({i,0});
	}
	for(int i=2;i<=n;++i) G[n+i].ZPB({n+i-1,0});
	for(int i=1;i<n;++i) G[(n<<1)+i].ZPB({(n<<1)+i+1,val[i+1].b-val[i].b});
	for(int i=1;i<=n;++i){
		int L=1,R=n,ans=n+1;
		while(L<=R){
			int mid=(L+R)>>1;
			if(val[i].a+val[mid].b>=m) R=mid-1,ans=mid;
			else L=mid+1;
		}
		if(ans>1) G[i].ZPB({n+ans-1,val[i].a});
		if(ans<=n) G[i].ZPB({(n<<1)+ans,val[i].a+val[ans].b-m});
	}
	priority_queue<Enode> q;
	for(int i=1;i<=(n<<1)+n;++i) dp[i]=LLmex;
	dp[st]=0,q.push({st,0});
	while(q.size()){
		Enode dt=q.top();
		q.pop();
		int x=dt.v;
		if(dp[x]<dt.w) continue;
		for(int i=0;i<(int)G[x].size();++i){
			int u=G[x][i].v;
			LL w=G[x][i].w;
			if(dp[u]>dp[x]+w) dp[u]=dp[x]+w,q.push({u,dp[u]});
		}
	}
	cout<<dp[ed]<<"\n";
	return 0;
}

评论

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

正在加载评论...