[ABC232G] Modulo Shortest Path
题意翻译
你有一个 $n$ 个点的有向完全图。
每个点有两个属性 $a_i$ 和 $b_i$。$u \to v$ 的边的权值是 $(a_u+b_v) \bmod m$。
给你 $n$ , $m$ 和 $\{a_i\}$ 以及 $\{b_i\}$ , 求 $1$ 到 $n$ 的最短路。
题目描述
[problemUrl]: https://atcoder.jp/contests/abc232/tasks/abc232_g
$ 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
4 12
10 11 6 0
8 7 4 1
输出样例 #1
3
输入样例 #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 $
- 入力はすべて整数
### Sample Explanation 1
以下では、頂点 $ i $ を始点、頂点 $ j $ を終点とする有向辺を $ i\ \rightarrow\ 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 $ へのパス上の辺の重みの総和として考えられる最小値となります。