102326: [AtCoder]ABC232 G - Modulo Shortest Path
Description
Score : $600$ points
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$.
Sample Input 1
4 12 10 11 6 0 8 7 4 1
Sample 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$.
Sample Input 2
10 1000 785 934 671 520 794 168 586 667 411 332 363 763 40 425 524 311 139 875 548 198
Sample Output 2
462
Input
题意翻译
你有一个 $n$ 个点的有向完全图。 每个点有两个属性 $a_i$ 和 $b_i$。$u \to v$ 的边的权值是 $(a_i+b_i) \bmod m$。 给你 $n$ , $m$ 和 $\{a_i\}$ 以及 $\{b_i\}$ , 求 $1$ 到 $n$ 的最短路。Output
问题描述
我们有一个包含$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$的路径中边的最小可能总权重。
限制条件
- $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$表示从顶点$i$到顶点$j$的有向边。
- 边$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