import std.stdio, std.string, std.conv; import std.algorithm, std.math; import std.range; import std.container.rbtree, std.container.dlist; import std.container.binaryheap, std.container.array; import std.typecons; alias mstring = char[]; const long INF = 1L << 60L; const long mod = 1_000_000_000 + 7; void chmin (T)(ref T x, T y) { x = min(x, y); } void chmax (T)(ref T x, T y) { x = max(x, y); } // 単一の数値を取得 // readln.chomp.to!int; // or // int a; // readf("%s\n", a); // 複数の数値を取得(可変数個の場合推奨) // readln.chomp.split.map!(to!long).array // 複数の数値を取得(固定数個の場合、推奨) // int a, b; // readf("%s %s\n", &a, &b); // インデントを一個ずらして複数の数値を取得(累積和とかで1-indexedの方が良い時がある) // long[] vs = readln.chomp.split.map!(to!long).array; // vs = [0L] ~ vs; // 小数点は以下で指定 // double ret = 10.0; // writefln("%.12f", ret); // 配列の最後の要素は arr[$-1] でアクセスできる void main () { int x0, y0; readf("%s %s\n", &x0, &y0); int N = readln.chomp.to!int; auto info = new Tuple!(int, int, double)[](N + 1); info[0][0] = x0; info[0][1] = y0; info[0][2] = 0L; foreach (i; 1 .. N + 1) readf ("%s %s %s\n", &(info[i][0]), &(info[i][1]), &(info[i][2])); auto dist = new long[][](N + 1, N + 1); foreach (u; 0 .. N + 1) foreach (v; 0 .. N + 1) dist[u][v] = abs(info[v][0] - info[u][0]) + abs(info[v][1] - info[u][1]); auto ws = new double[](1 << N); foreach (s; 0 .. (1 << N)) { double tot = 0L; foreach (u; 1 .. N + 1) { if (s & (1 << (u - 1))) continue; tot += info[u][2]; } ws[s] = tot; } auto dp = new double[][](1 << N, N + 1); foreach (s; 0 .. (1 << N)) foreach (u; 0 .. N + 1) dp[s][u] = cast(double)(INF); dp[0][0] = 0.0; foreach (s; 0 .. (1 << N)) { foreach (u; 0 .. N + 1) { if (dp[s][u] == cast(double)(INF)) continue; foreach (v; 1 .. N + 1) { if (s & (1 << (v - 1))) continue; auto cst = dist[u][v] * (ws[s] + 100.0) / 120.0; chmin(dp[s | (1 << (v - 1))][v], dp[s][u] + cst); } } } double ret = cast(double)(INF); foreach (u; 1 .. N + 1) { auto cst = dist[u][0] * 100.0 / 120.0; chmin(ret, dp[(1 << N) - 1][u] + cst); } writefln("%.12f", ret + ws[0]); }