問題一覧 > 通常問題

No.1690 Power Grid

レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 106
作問者 : ansainansain / テスター : LayCurseLayCurse 👑 ygussanyygussany
0 ProblemId : 6622 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-09-24 23:04:19

問題文

yukicoder王国には都市 $1$ から都市 $N$ までの $N$ 個の都市と、$M$ 本の道路があります。
都市 $i\ (1 \le i \le N)$ の人口は $A_i$ です。$i\ (1 \le i \le M)$ 本目の道路は都市 $X_i$ と $Y_i$ を双方向に結び、その長さは $Z_i$ です。
王国の任意の $2$ つの都市間は、いくつかの道路を通って双方向に行き来可能です。

ansain国王は順番に $K$ 個の都市に発電所を建設することにしました。
$1$ 個目の発電所を建設するときのコストは都市 $i$ に建設するとき、$A_i$ かかります。
$2$ 個目以降の発電所については、都市 $i$ に建設するとき、$A_i$ に加えて、都市 $i$ から最も近い建設済みの発電所がある都市までの距離のコストがかかります。
ただし、都市 $i,j$ 間の距離は、都市 $i$ から都市 $j$ まで移動するのに通る道路の長さの和の最小値です。

$K$ 個の都市に発電所を建設するときにかかるコストの最小値を求めてください。

入力

$N\ M\ K$
$A_1$ $A_2$ $\dots$ $A_N$
$X_1$ $Y_1$ $Z_1$
$X_2$ $Y_2$ $Z_2$
$\vdots$
$X_M$ $Y_M$ $Z_M$

  • $1 \le N \le 18$
  • $N-1 \le M \le N(N-1)/2$
  • $1 \le K \le N$
  • $1 \le A_i \le10^9$
  • $1 \le X_i < Y_i \le N$
  • $i \neq j $ であれば $(X_i,Y_i) \neq (X_j,Y_j)$
  • $1 \le Z_i \le 10^9$
  • 入力は全て整数
  • 王国の任意の $2$ つの都市間は、いくつかの道路を通って双方向に行き来可能なことが保証される
  • 出力

    $K$ 個の都市に発電所を建設するときにかかるコストの最小値を出力してください。最後に改行してください。

    サンプル

    サンプル1
    入力
    3 2 2
    3 5 8
    1 2 9
    2 3 2
    出力
    15

    最適に発電所を建設する方法の一例は以下の通りです。

  • $1$ 個目を都市 $2$ に建てる。コストは $5$ かかる。
  • $2$ 個目を都市 $3$ に建てる。コストは $8$ に加え、都市 $3$ から都市 $2$ までの距離である $2$ かかる。
  • 合計で $15$ のコストがかかります。

    サンプル2
    入力
    4 3 3
    10000 1 1 1
    1 2 1
    1 3 2 
    1 4 1
    出力
    8

    最適に発電所を建設する方法の一例は以下の通りです。

  • $1$ 個目を都市 $2$ に建てる。コストは$1$かかる。
  • $2$ 個目を都市 $3$ に建てる。コストは$1$に加え、都市 $3$ から都市 $2$ までの距離である $3$ かかる。
  • $3$ 個目を都市 $4$ に建てる。コストは$1$に加え、都市 $2,3$ のうち、都市 $4$ に最も近い都市 $2$ までの距離である $2$ かかる。
  • 合計で $8$ のコストがかかります。

    サンプル3
    入力
    10 10 1
    1 10 100 1000 10000 100000 1000000 10000000 100000000 1000000000
    1 2 1
    2 3 10
    3 4 100
    4 5 1000
    5 6 10000
    6 7 100000
    7 8 1000000
    8 9 10000000
    9 10 100000000
    1 10 1000000000
    出力
    1

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