M-SOLUTIONS プロコンオープン2021(AtCoder Beginner Contest 232)
翻译中…
Problem Statement
翻译中…
We have a directed graph with $N$ vertices, called Vertex $1$, Vertex $2$, $\ldots$, Vertex $N$.
翻译中…
For each pair of integers such that $1 \leq i, j \leq N$ and $i \neq j$, there is a directed edge from Vertex $i$ to Vertex $j$ of weight $(A_i + B_j) \bmod M$. (Here, $x \bmod y$ denotes the remainder when $x$ is divided by $y$.)
翻译中…
There is no edge other than the above.
翻译中…
Print the shortest distance from Vertex $1$ to Vertex $N$, that is, the minimum possible total weight of the edges in a path from Vertex $1$ to Vertex $N$.
翻译中…
Constraints
翻译中…
$2 \leq N \leq 2 \times 10^5$$2 \leq M \leq 10^9$$0 \leq A_i, B_j < M$- All values in input are integers.
翻译中…
Input
翻译中…
Input is given from Standard Input in the following format:
翻译中…
N M
A_1 A_2 \ldots A_N
B_1 B_2 \ldots B_N翻译中…
Output
翻译中…
Print the minimum possible total weight of the edges in a path from Vertex $1$ to Vertex $N$.
翻译中…
样例
Input #1
4 12
10 11 6 0
8 7 4 1
Output #1
3
Below, $i \rightarrow j$ denotes the directed edge from Vertex $i$ to Vertex $j$.
Let us consider the path $1$ $\rightarrow$ $3$ $\rightarrow$ $2$ $\rightarrow$ $4$.
- Edge $1\rightarrow 3$ weighs $(A_1 + B_3) \bmod M = (10 + 4) \bmod 12 = 2$,
- Edge $3 \rightarrow 2$ weighs $(A_3 + B_2) \bmod M = (6 + 7) \bmod 12 = 1$,
- Edge $2\rightarrow 4$ weighs $(A_2 + B_4) \bmod M = (11 + 1) \bmod 12 = 0$.
Thus, the total weight of the edges in this path is $2 + 1 + 0 = 3$.
This is the minimum possible sum for a path from Vertex $1$ to Vertex $N$.
Input #2
10 1000
785 934 671 520 794 168 586 667 411 332
363 763 40 425 524 311 139 875 548 198
Output #2
462
题目信息
题面与样例版权归 AtCoder 及出题人所有；中文翻译由 AI 生成（CI 管线），如有出入请以原文为准。