No.134 走れ!サブロー君

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 小数誤差許容問題 絶対誤差または相対誤差が$10^{-7}$ 以下
タグ : / 解いたユーザー数 85
作問者 : なおなお
1 ProblemId : 273 / 出題時の順位表

問題文

サブロー君は酒屋で働いており、注文された商品をトラックで配達しようとしています。
出発地点である酒屋とすべての配達先は2次元平面上にあり、それぞれの位置は、
$(X_0,\ Y_0)$が酒屋の座標、そして$N$件の配達先は$(X_i,\ Y_i)$の座標で表されます。$(1 \leq i \leq N)$
各配達先$i$では、重さ$W_i$の商品をトラックから降ろして渡します。

この町は、碁盤の目状に道が整備されており、
各地点から任意の地点まで、南北方向(Y軸)または東西方向(X軸)に移動することができますが、
荷物の重さ$W$を積んでいるとき、1単位距離を移動するためには、以下の式で表される時間$T$が掛かります。
\[ T = \frac{W+100}{120} \]
また、各配達先$i$で重さ$W_i$の荷物を降ろすのに時間$W_i$が掛かります。

酒屋ですべての荷物をトラックに積んで各配達先を周り
すべての配達先へ荷物を配達し終わり、酒屋へ戻ってくるまでの最短時間を求めてください。

・トラックには、配達する荷物以外のものを積むことはありません。
・移動の途中で何らかの理由で停止や減速することはなく、等速で移動し続けられるものとします。
・最初に荷物を積む時間は含みません。

入力

$X_0$ $Y_0$
$N$
$X_1$ $Y_1$ $W_1$
$X_2$ $Y_2$ $W_2$
$\dots$
$X_i$ $Y_i$ $W_i$
$\dots$
$X_N$ $Y_N$ $W_N$

$1$行目に酒屋の位置を表す整数 $X_0,\ Y_0$ が与えられます。
$2$行目に配達先の数を表す整数 $N\ (1 \leq N \leq 13)$ が与えられます。
続く$N$行に、各配達先の位置を表す整数$(X_i,\ Y_i)$、配達する荷物の重さ 小数点6桁までで記述される小数または整数 $W_i\ (1 \leq W_i \leq 100)$,がスペース区切りで与えられます。$(1 \leq i \leq N)$
酒屋および配達先の位置はすべて、$(0 \leq X_i,\ Y_i \leq 1000)$の範囲にあります。

出力

すべての荷物を配達し終わるまでの最短時間を出力してください。
誤差は絶対誤差あるいは相対誤差の少なくとも片方が \(10^{−7}\) 以下であれば許容されます。

サンプル

サンプル1
入力
0 0
3
100 178 100
23 25 40
34 31 90
出力
989.75

酒屋から出発して配達先$2$、配達先$3$、配達先$1$の順に周ることで最短時間で配達することができます。

サンプル2
入力
0 0
5
0 0 100
0 0 100
0 0 100
0 0 100
0 1000 1
出力
2076

酒屋と配達先が同一の位置にあったり、同一の位置に配達先が複数ある場合もあります。
$1$件目から$4$件目までは移動は不要なので、荷物を降ろすのに合計で時間 $400$ が掛かります。
次に$5$軒目へ配達するのに時間 $842.666667$ が掛かり、さらに酒屋へ戻る時間 $833.333333$ を合計して解になります。

サンプル3
入力
10 10
1
10 10 1.2
出力
1.2

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

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