問題一覧 > 通常問題

No.1480 Many Complete Graphs

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 48
作問者 : PCTprobabilityPCTprobability / テスター : 👑 fairy_lettucefairy_lettuce 蜜蜂蜜蜂 nok0nok0 ygussanyygussany
5 ProblemId : 5945 / 出題時の順位表
問題文最終更新日: 2021-04-16 23:06:03

evilケースについて

本問題で、想定していなかった枝刈り解法が通ってしまうことが発覚したため evil ケースとして制約を $2$ 倍にしたケースを evil ケースとして追加することにします。

申し訳ありません。

問題文

頂点に $1$ から $N$ の番号がついた $N$ 頂点 $0$ 辺の無向グラフがあります。このグラフに対し、以下の操作を $M$ 回行います。

$i$ 回目の操作では正整数 $k_i,c_i$ と長さ $k_i$ の数列 $s_1,s_2,\dots,s_{k_i}$ が与えられます。 $1\le x < y \le k_i$ を満たす全ての整数の組$(x,y)$ に対し、 頂点 $s_x$ と頂点 $s_y$ を結ぶ長さ $\displaystyle \left\lceil{\frac{s_x+s_y}{2}}\right\rceil + c_i$ の無向辺を貼ります。 ただし、 $\displaystyle \lceil x \rceil$ は 実数 $x$ 以上の最小の整数のことを表します。

$M$ 回の操作が終了した時点でのグラフにおいて、頂点 $1$ から頂点 $N$ へのパスの長さの最小値を求めてください。

ただし、頂点 $1$ から頂点 $N$ へのパスが存在しない場合は代わりに $-1$ を出力してください。

入力

$N\ M$
$k_1\ c_1\ s_{1,1}\ s_{1,2}\ ...\ s_{1,k_1}$
$k_2\ c_2\ s_{2,1}\ s_{2,2}\ ...\ s_{2,k_2}$
$\vdots$
$k_M\ c_M\ s_{M,1}\ s_{M,2}\ ...\ s_{M,k_M}$

  • 入力は全て整数である。
  • $1 \le N \le 10^5$
  • $0 \le M \le 10^5$
  • $2 \le k_i \le N$
  • $1 \le c_i \le 10^9$
  • $1 \le s_{i,1} < s_{i,2} < ... < s_{i,k_i} \le N$
  • $ \displaystyle \sum_{i=1}^{M}k_i \le 10^5$
  • 以下は evil ケースの制約です。このケースは正誤判定に影響しません。一番下の制約のみが変わっています。

  • 入力は全て整数である。
  • $1 \le N \le 10^5$
  • $0 \le M \le 10^5$
  • $2 \le k_i \le N$
  • $1 \le c_i \le 10^9$
  • $1 \le s_{i,1} < s_{i,2} < ... < s_{i,k_i} \le N$
  • $ \displaystyle \sum_{i=1}^{M}k_i \le 2 \times 10^5$
  • 出力

    $M$ 回の操作が終了した時点でのグラフにおいて、頂点 $1$ から頂点 $N$ へのパスの長さの最小値を求めてください。

    ただし、頂点 $1$ から頂点 $N$ へのパスが存在しない場合は代わりに $-1$ を出力してください。

    サンプル

    サンプル1
    入力
    3 1
    3 1 1 2 3
    出力
    3

    $1$ 回目の操作で頂点 $1,2$ の間には長さ $3$ の辺が、頂点 $1,3$ の間には長さ $3$ の辺が、頂点 $2,3$ の間には長さ $4$ の辺が張られます。 全ての操作が終わった後の、頂点 $1$ から頂点 $3$ への最短パスの長さは $3$ です。

    サンプル2
    入力
    8 2
    4 1000000000 1 2 3 4
    4 1000000000 5 6 7 8
    出力
    -1

    頂点 $1$ から頂点 $N$ へのパスが存在しないこともあります。

    サンプル3
    入力
    18 8
    6 11 1 3 5 6 9 13
    10 20 2 3 4 6 7 10 13 14 16 17
    9 10 1 4 5 10 11 13 14 16 17
    10 6 4 5 7 10 11 13 14 15 16 18
    2 9 5 12
    9 4 2 4 6 8 9 10 14 15 16
    7 18 1 2 4 8 10 11 18
    4 17 2 3 8 10
    出力
    28

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