ABC232G Modulo Shortest Path 做题记录

有一个 $n$ 个节点的有向图 $G$，对于所有的 $1 \le i, j \le n$ 且 $i \not= j$，都有一条权值为 $(a_i + b_j) \bmod m$ 的边连接 $i$ 和 $j$，请你求出 $G$ 从 $1$ 到 $n$ 的最短路。

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

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

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

所以可以 $i\to(m-a_i)'$ 连一条长度为 $0$ 的边，$b_i'\to i$ 连一条长度为 $0$ 的边，跑 $1$ 到 $n$ 的最短路即可。

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

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