A - かえってきたどうぶつたち と しんりんのさいせい (Return of Animals and Regeneration of Forests) Editorial /

Time Limit: 0 msec / Memory Limit: 256 MB

かつて豊かな森林だったある地は人間たちによって荒らされてしまい、そこで暮らしていたどうぶつたちも姿を消しました。これはその少し後の話です。

これまで好き放題していた人間たちは、ようやく地球のあげる悲鳴に気がつきました。人間たちは過去の行いを悔い、環境を守り失われた森林を再生する活動を始めました。

きつねの次郎たちが暮らしていた場所にも少しずつではありますが緑が帰ってきました。次郎とその仲間のどうぶつたちは、暮らし慣れた場所でもう一度楽しく過ごしたいと思ってその場所へ帰ってきました。

新しく再生された森林にもどうぶつたちの遊び場があります。どうぶつたちは遊び場を結ぶ道をもう一度作りなおして、遊び場どうしの行き来ができるようにしようと思いましたが、新しい森林にはまだ慣れきっていないのでできるだけシンプルな道を作ることにしました。

具体的には、どの遊び場からどの遊び場へもちょうど 1 通りの経路があるようにします。こうすれば新しい森でも迷う心配なく遊び場へと行くことができます。そのような道の作り方はきっとたくさんあるので、その中で道の長さの合計がいちばん小さくなるようにしましょう。

どうぶつたちが新しい森で快適に過ごすための手伝いをしてもらえないでしょうか。

課題

はじめ 1 つの頂点のみからなるグラフに頂点と辺と追加していき、最終的には頂点の数を N 個にする。最初からある頂点には番号 0 がつけられており、頂点 i の直後に追加される頂点には番号 i+1 がつけられる。

次のプロシージャを実装せよ:

  • 次のパラメータを持つプロシージャ construct(N, M, E):
    • N -- 頂点の数。各頂点は、追加される順に0からN-1まで番号がつけられている。
    • M -- 使用可能な辺の数。
    • E -- 使用可能な辺の情報を表す 2 次元配列. 0 ≦ i ＜ M に対し, 辺 i は頂点 E[i][0] と E[i][1] を結んでいて、その長さはE[i][2]である。0 ≦ E[i][0] ＜ E[i][1] ＜ N, 1 ≦ E[i][2] ≦ 1 000 000 000を仮定してよい。
    このプロシージャはanswer(C)をN-1回呼び出す必要がある。x回目の呼び出し(1 ≦ x ≦ N-1)では、0以上x以下の番号をもつ頂点同士が、x+1以上の番号をもつ頂点を通らずに互いに一通りの方法で行き来できるようにするために必要な辺の長さの合計のうち、最小のものをCとすること。ただし、そのような辺の組み合わせが存在しない場合はC = -1とせよ。

例

図1
図 1

図1に示される N = 5, M = 8,

E = 0 1 8
0 2 7
0 3 1
1 2 3
1 4 7
2 3 2
2 4 6
3 4 9

の場合を考える。この場合、constructはanswerを4回呼ばなければならない。以下に正しいanswerの呼び出し方法を示す:

回数(x) 呼び出し
1 answer(8)
2 answer(10)
3 answer(6)
4 answer(12)

小課題

以下、1回の実行における construct 呼び出しのパラメータ P の総和、すなわち最終的にできあがるグラフの辺の数を M とする。

小課題 1 (16 点)

  • 1 ≦ N ≦ 1 000
  • 0 ≦ M ≦ 2 000

小課題 2 (24 点)

  • 1 ≦ N ≦ 5 000
  • 0 ≦ M ≦ 60 000

小課題 3 (59 点)

  • 1 ≦ N ≦ 20 000
  • 0 ≦ M ≦ 60 000

小課題 4 (1 点)

  • 1 ≦ N ≦ 100 000
  • 0 ≦ M ≦ 200 000

実装の詳細

制限

  • CPU 時間制限: 1.5 秒
  • メモリ制限: 256 MB
    注意: スタックのサイズには決められた制限はない。スタックとして使用されたメモリは、メモリ総使用量に含まれる。

インターフェース (API)

  • 実装フォルダ: animals2/ (プロトタイプ: animals2.zip)
  • 競技者が実装するファイル: animals2.cpp
  • 提出ファイルのインターフェース: animals2.h
  • 採点プログラムのサンプル: grader.cpp
  • 採点プログラムの入力のサンプル: grader.in.1, grader.in.2, ...
    注意:採点プログラムのサンプルは次の書式の入力を読み込む。
    • 1 行目: N, M が空白区切りで書かれている。
    • 2 行目から M+1 行目: 0 ≦ i ＜ M に対し、i+2 行目には 3 つの整数 E[i][0], E[i][1], E[i][2] が空白区切りで書かれている。
  • 採点プログラムの入力のサンプルに対して期待される出力: grader.expect.1, grader.expect.2, ...
    注意:採点プログラムのサンプルは次の書式の出力を書き出す。
    • 1 行目から N-1 行目: 0 ≦ i ＜ N-1 に対し、i+1 行目には constructがi 回目に answer を呼び出したときの戻り値が書かれている。