No.788 トラックの移動

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 54
作問者 : tatyamtatyam / テスター : Shuz*Shuz*
6 ProblemId : 2526 / 出題時の順位表

問題文

tatyam国には $1$ 番から $N$ 番までの $N$ 個の交差点とそれらをつなぐ $M$ 本の道路があり、交差点 $a_i$ と交差点 $b_i$ が長さ $c_i$ の道路で繋がっています。
tatyam国では祭りが行われ、そこでトラックが90度回転することがあります。 tatyamは今度の祭りに備え、トラックを1つの交差点に集めようと考えています。
tatyamは1台のレッカー車を持っており、レッカー車は1台のトラックを持ち上げて運ぶことができます。
レッカー車は交差点 $L$ に停まっていて、交差点 $i$ には $t_i$ 台のトラックが停まっています。
レッカー車をできるだけ短い移動距離で動かして全てのトラックを1つの交差点に集める時、その移動距離を求めてください。

入力

$N\ M\ L$
$t_1\ \cdots\ t_N$
$a_1\ b_1\ c_1$
$\vdots$
$a_m\ b_m\ c_m$

$2\leq N\leq 2000$
$N-1\leq M\leq 2000$
$0\leq t_i\leq 2000$
$1\leq\sum t_i$
$1\leq L,\ a_i,\ b_i\leq N$
$1\leq c_i\leq 10^6$
与えられる交差点と道路でできるグラフは連結である

出力

レッカー車をできるだけ短い移動距離で動かして全てのトラックを1つの交差点に集める時、その移動距離を出力してください。 最後に改行してください。

サンプル

サンプル1
入力
4 3 1
0 1 1 1
1 2 1
1 3 2
1 4 3
出力
12

例えば、以下のようにすると最短になります。
頂点1から頂点2に移動しトラックを持ち上げる
頂点2から頂点1に移動しトラックを下ろす
頂点1から頂点3に移動しトラックを持ち上げる
頂点3から頂点1に移動しトラックを下ろす
頂点1から頂点4に移動しトラックを持ち上げる
頂点4から頂点1に移動しトラックを下ろす

サンプル2
入力
5 5 1
0 2 1 1 2
1 2 1
1 3 2
2 4 2
3 4 2
4 5 2
出力
19

例えば、以下のようにすると最短になります。
1→2
2→4
4→2
2→4
4→3
3→4
4→5
5→4

サンプル3
入力
7 9 1
1 1 1 1 1 1 1
1 7 3
2 3 3
2 5 4
3 4 5
3 5 1
3 7 6
4 6 2
5 6 7
6 7 9
出力
53

例えば、以下のようにすると最短になります。
1→7
7→3
3→2
2→3
3→4
4→3
3→5
5→3
3→4
4→6
6→4
4→3
3→7
7→3

提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。