問題一覧 > 通常問題

No.134 走れ!サブロー君

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 小数誤差許容問題 絶対誤差または相対誤差が$10^{-7}$ 以下。ただし、ジャッジ側の都合で500桁未満にしてください
タグ : / 解いたユーザー数 146
作問者 : なおなお
1 ProblemId : 273 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2016-07-14 20:09:47

問題文

サブロー君は酒屋で働いており、注文された商品をトラックで配達しようとしています。
出発地点である酒屋とすべての配達先は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

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