問題一覧 > 通常問題

No.788 トラックの移動

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 93
作問者 : 👑 tatyamtatyam / テスター : Shuz*Shuz*
8 ProblemId : 2526 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2020-06-09 16:25:11

問題文

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つの交差点にある場合は 0 を出力してください。
最後に改行してください。

サンプル

サンプル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
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

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