ABC232G Modulo Shortest Path 做题记录

有一个 nn 个节点的有向图 GG,对于所有的 1i,jn1 \le i, j \le ni=ji \not= j,都有一条权值为 (ai+bj)modm(a_i + b_j) \bmod m 的边连接 iijj,请你求出 GG11nn 的最短路。

发现取模不好处理,那么考虑构造一个”取模装置“:建立 mm 个点 0,1,2,3,,(m1)0',1',2',3',\dots,(m-1)'i(i+1)i'\to (i+1)' 连一条权值为 11 的边,特别的,(m1)0(m-1)'\to0' 连一条权值为 11 的边。

然后建出原来的 nn 个节点,但是这个”取模装置“只能处理减法的取模,考虑用一个式子把加法转换成减法:

(x+y)modm=y(mx)modm(x+y)\operatorname{mod}m=y-(m-x)\operatorname{mod} m

所以可以 i(mai)i\to(m-a_i)' 连一条长度为 00 的边,biib_i'\to i 连一条长度为 00 的边,跑 11nn 的最短路即可。

但是 mm10910^9 级别的,把”取模装置“建完肯定空间和时间都会爆炸。观察到”取模装置“上的点有很多都是没有原来的节点与之相连的,这些点就可以直接缩掉,像这样:

缩点操作可以使用离散化来实现,建好图之后跑一边 dijkstra 即可。