分数: 600 点
问题陈述
我们有一个有向图 N 顶点,称为 Vertex 1,顶点 2, \ldots,顶点 N.
对于每对整数,使得 1 \leq i, j \leq N 和 i \neq j,有一条来自 Vertex 的有向边 i 到顶点 j 的重量 (A_i + B_j) \bmod M。 (这里, x \bmod y 表示当 x 除以 y.)
除上述以外没有其他边缘。
打印距顶点的最短距离 1 到顶点 N,即从 Vertex 开始的路径中边的最小可能总权重 1 到顶点 N.
约束
- 2 \leq N \leq 2 \times 10^5
- 2 \leq M \leq 10^9
- 0 \leq A_i, B_j < M
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N M A_1 A_2 \ldots A_N B_1 B_2 \ldots B_N
输出
打印从顶点开始的路径中边的最小可能总权重 1 到顶点 N.
示例输入 1
4 12 10 11 6 0 8 7 4 1
示例输出 1
3
下面, i \rightarrow j 表示来自 Vertex 的有向边 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.
示例输入 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