Finals(本選会場) - joi2010-day3

出典: 第9回日本情報オリンピック 春季トレーニング合宿

時間制限: 1秒

メモリ制限: 64MB

JOI国にはN個の都市があり, 1からNの番号がついている. また, M本の道路がある. 全ての道路は異なる2つの都市を結び, 双方向に通行可能である. JOI国の任意の2つの都市は, 道路をたどって片方からもう片方へ到達可能である. JOI国の道路は全て有料道路であり, 道路ごとに通行料金が決まっている.

JOI国でも情報オリンピックは開催される. JOI国の情報オリンピックの本選には, 各都市の代表選手が出場する. 本選をどの都市で開催するかを決定し, 選手をそれらの都市に集めるためにかかる金額を見積もっておく必要がある. 本選はK個の都市で開催し, 本選の際には全ての選手をそれらのいずれかの都市に移動させなければならない. 1つの都市に集まる選手の人数に制限はない.

本選を開催する都市に選手を集める際には, 道路を利用する. 通行料金がcの道路は, 一度に何人で通行しても料金はcである. そこで, 選手を移動させる順番を工夫することによって, 複数の選手を一度に通行させるようにすれば, 料金を節約することができる.

本選を開催する都市を決定し, 選手を本選会場に集める際にかかる通行料金の和を最小化したい.

課題(TASK)

N, M, K と全ての道路の情報が与えられたとき, 選手を本選会場に集める際にかかる通行料金の和の最小値を計算するプログラムを作成せよ

制限(CONSTRAINTS)

1 ≤ N ≤ 100,000	都市の数
1 ≤ M ≤ 100,000	道路の数
1 ≤ K ≤ N	本選を開催する都市の個数
1 ≤ A[i] < B[i] ≤ N	道路iの結ぶ2つの都市
1 ≤ C[i] ≤ 100	道路iの通行料金

入力(INPUT)

標準入力から以下の入力を読み込め.

• 1行目には整数N, M, K が空白を区切りとして書かれている.
• 続くM行には, 1行につき1つの道路について記述されている. これらの行のうちのi行目は道路iについて記述しており, 整数A[i], B[i], C[i] が空白を区切りとして書かれている.

出力(OUTPUT)

標準出力に選手を本選会場に集める際にかかる金額の最小値を表す1つの整数を出力せよ.

採点基準(GRADING)

40点分のテストグループにおいて, N ≤ 1,000 である.

40点分のテストグループにおいて, K = 1 である.

20点分のテストグループは, これら2つの条件の両方をみたす.

60点分のテストグループは, これら2つの条件の少なくとも一方をみたす.

入出力例(EXAMPLE)

入力例(Sample Input)	出力例(Sample Output)
4 3 1 1 2 2 2 3 9 2 4 5	16

例えば, 都市1で本選を開催するとし, まず都市4の代表選手を都市2へ移動させ, 次に都市3の代表選手を都市2へ移動させ, 都市2に居る3人の選手を都市1へ移動させればよい.

入力例(Sample Input)	出力例(Sample Output)
5 6 2 1 2 5 1 3 3 2 3 4 2 5 7 3 4 6 4 5 5	12

例えば, 都市3と都市4で本選を開催するとし, 都市1, 2 の代表選手は都市3へ, 都市5の代表選手は都市4へ集めればよい.