問題一覧 > 通常問題

No.596 郵便配達

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 6
作問者 : 37zigen / テスター : はむこ
ProblemId : 1367 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2020-01-10 16:52:46
コンテストの他の問題:

問題文

数直線上に家とポストが並んでいます。
ポストには宛先の家が記載された郵便物が投函されています。
全ての郵便物をポストから回収し宛先の家まで届けなければなりません。
必要な最小移動距離を求めてください。

配達の際の始点と終点は自由に選べるとします。
また郵便物は一度に何個でも運べるとします。

入力

$N$ $M$
$x_1$ $d_1$
$y_1$ $y_2$ $y_3$ ⋯⋯ $y_{d_1}$
$x_2$ $d_2$
$y_1$ $y_2$ $y_3$ ⋯⋯ $y_{d_2}$
$\vdots$
$x_M$ $d_M$
$y_1$ $y_2$ $y_3$ ⋯⋯ $y_{d_M}$

$1 \leq N \leq 7×10^6$
$1 \leq M \leq 5×10^5$
$0 \leq x_i < N$
$0 \leq y_i < N$
$1 \leq d_i ∧ \sum{d_i} \leq 10^6$

[$0$,$N$)の整数座標上に家とポストが位置する。$M$はポストの数。
$x_i$は$i$番目のポストの位置。
$d_i$は$i$番目のポストに含まれる郵便物の数。
$x_i$ $d_i$に続く行の$y_j$は$i$番目のポストの$j$番目の手紙の宛先の家の位置。

郵便物の宛先の座標と投函されているポストの座標は、同じ場合があることに注意してください。

出力

全ての郵便物を宛先まで届けるのに必要な最小移動距離を求めてください。

サンプル

サンプル1
入力
6 1
0 1
1
出力
1

サンプル2
入力
9 4
0 3
2 7 6
6 2
8 5
1 4
2 7 0 1
4 2
1 6
出力
14

サンプル3
入力
10 5
5 1
1
9 2
0 4
6 3
8 7 2
1 4
2 7 0 1
4 2
1 6
出力
17

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。