Modulo Shortest Path

题目描述

我们有一个有向图，包含 $N$ 个顶点，分别称为 顶点 $1$、顶点 $2$、$\ldots$、顶点 $N$。 对于所有满足 $1 \leq i, j \leq N$ 且 $i \neq j$ 的整数对，存在一条从 顶点 $i$ 到 顶点 $j$ 的有向边，其权重为 $(A_i + B_j) \bmod M$。（这里，$x \bmod y$ 表示 $x$ 除以 $y$ 的余数。） 除此之外不存在其他边。 打印从 顶点 $1$ 到 顶点 $N$ 的最短距离，也就是从 顶点 $1$ 到 顶点 $N$ 的路径中边权总和的最小可能值。

输入格式

输入通过标准输入按以下格式给出： $N$ $M$ $A_1$ $A_2$ $\ldots$ $A_N$ $B_1$ $B_2$ $\ldots$ $B_N$

输出格式

打印从 顶点 $1$ 到 顶点 $N$ 的路径中边权总和的最小可能值。

4 12
10 11 6 0
8 7 4 1

3

10 1000
785 934 671 520 794 168 586 667 411 332
363 763 40 425 524 311 139 875 548 198

462

提示

$2 \leq N \leq 2 \times 10^5$ $2 \leq M \leq 10^9$ 0 \leq A_i, B_j < M 输入中的所有数值均为整数。下面，$i \rightarrow j$ 表示从 顶点 $i$ 到 顶点 $j$ 的有向边。
我们考虑路径 $1$ $\rightarrow$ $3$ $\rightarrow$ $2$ $\rightarrow$ $4$。

边 $1\rightarrow 3$ 的权重为 $(A_1 + B_3) \bmod M = (10 + 4) \bmod 12 = 2$， 边 $3 \rightarrow 2$ 的权重为 $(A_3 + B_2) \bmod M = (6 + 7) \bmod 12 = 1$， 边 $2\rightarrow 4$ 的权重为 $(A_2 + B_4) \bmod M = (11 + 1) \bmod 12 = 0$。

因此，该路径的边权总和为 $2 + 1 + 0 = 3$。
这是从 顶点 $1$ 到 顶点 $N$ 的路径的最小可能和。

标签: AtCoder|abc232G

来源

AtCoder|abc232G