有一个 n 个节点的有向图 G,对于所有的 1≤i,j≤n 且 i=j,都有一条权值为 (ai+bj)modm 的边连接 i 和 j,请你求出 G 从 1 到 n 的最短路。
发现取模不好处理,那么考虑构造一个”取模装置“:建立 m 个点 0′,1′,2′,3′,…,(m−1)′,i′→(i+1)′ 连一条权值为 1 的边,特别的,(m−1)′→0′ 连一条权值为 1 的边。
然后建出原来的 n 个节点,但是这个”取模装置“只能处理减法的取模,考虑用一个式子把加法转换成减法:
(x+y)modm=y−(m−x)modm
所以可以 i→(m−ai)′ 连一条长度为 0 的边,bi′→i 连一条长度为 0 的边,跑 1 到 n 的最短路即可。
但是 m 是 109 级别的,把”取模装置“建完肯定空间和时间都会爆炸。观察到”取模装置“上的点有很多都是没有原来的节点与之相连的,这些点就可以直接缩掉,像这样:
缩点操作可以使用离散化来实现,建好图之后跑一边 dijkstra 即可。