Modulo Shortest Path 题解

思路

原图有 $\Theta(N^2)$ 条边，不能直接建图。边权 $(A_i+B_j)\bmod M$ 可看成在模 $M$ 环上从 $(-A_i)\bmod M$ 顺时针走到 $B_j$ 的距离。因此只需保留所有这两类关键坐标。

做法

25 分

若所有 $A_i+B_j<M$，任意路径 $1=v_0,v_1,\ldots,v_k=N$ 的权值可重排为

后一部分非负，所以直达边必然最优，答案为 $A_1+B_N$。

累计 60 分

当 $N\le2000$ 时，在不存储边的情况下运行稠密 Dijkstra。每轮线性选取距离最小的未确定顶点，再枚举所有终点并现算模边权，复杂度为 $O(N^2)$。

100 分

收集所有 $(M-A_i)\bmod M$ 和 $B_i$，排序去重后得到关键坐标环。建立原顶点与坐标顶点：

• 从原顶点 $i$ 向坐标 $(M-A_i)\bmod M$ 连零边；
• 从坐标 $B_i$ 向原顶点 $i$ 连零边；
• 每个坐标向环上下一个坐标连边，权值为顺时针模差。

从 $i$ 经其入口坐标走到 $B_j$、再经零边进入 $j$，代价恰为 $(A_i+B_j)\bmod M$。反向也可将辅助图中相邻两个原顶点之间的片段还原成原图边；回到同一原顶点的闭游走非负，删除不会变差。因此两图最短路相等。

对至多 $3N$ 量级的点和 $O(N)$ 条边运行堆优化 Dijkstra。必须保留最大坐标到最小坐标的跨环边，并用 64 位整数表示距离和环差。

正确性证明

每条原图边都有一条同权的辅助图路径，因此辅助图最短距离不大于原图。任意辅助图路径在相邻原顶点间又恰好对应一条同权原图边，非负闭游走可删，所以原图最短距离也不大于辅助图。两者相等，Dijkstra 给出正确答案。

复杂度

满分算法时间复杂度为 $O(N\log N)$，空间复杂度为 $O(N)$。