AT_abc232_g [ABC232G] Modulo Shortest Path

题目描述

有一个包含 $N$ 个顶点的有向图。$N$ 个顶点分别被称为顶点 $1$、顶点 $2$、$\ldots$、顶点 $N$。

对于每一组满足 $1 \leq i, j \leq N$ 且 $i \neq j$ 的整数对 $(i, 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$ 的路径上所有边权之和的最小值。

输入输出样例 #1

输入 #1

4 12
10 11 6 0
8 7 4 1

输出 #1

3

输入输出样例 #2

输入 #2

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

输出 #2

462

说明/提示

限制条件

• $2 \leq N \leq 2 \times 10^5$
• $2 \leq M \leq 10^9$
• $0 \leq A_i, B_j < M$
• 输入均为整数

样例解释 1

如下所示，用 $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$ 的路径上所有边权之和的最小值。

由 ChatGPT 4.1 翻译