#include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; typedef pair P; #define MOD 1000000007 // 10^9 + 7 #define INF 1000000000 // 10^9 #define LLINF 1LL<<60 int X[14], Y[14]; double W[14]; double dp[1 << 14][14]; // dp[i][j] : 最後がjであるときの最短時間 int main() { cin.tie(0); ios::sync_with_stdio(false); cin >> X[0] >> Y[0]; int N; cin >> N; for (int i = 1; i <= N; i++) cin >> X[i] >> Y[i] >> W[i]; W[0] = 0; N++; for (int i = 0; i < (1 << N); i++) { for (int j = 0; j < N; j++) dp[i][j] = INF; } dp[1][0] = 0; for (int i = 1; i < (1 << N); i++) { for (int cur = 0; cur < N; cur++) { if (1 & (i >> cur)) { // curが行ったことになってるとき double weight = 0; // 現在詰んでいる荷物の総量 for (int k = 1; k < N; k++) if (!(1 & (i >> k))) weight += W[k]; // まだ行ってなかったら、その荷物を持っている for (int nxt = 1; nxt < N; nxt++) { if (!(1 & (i >> nxt))) { // nxtに行ってなかったら double T = (weight + double(100)) / double(120); double d = abs(X[cur] - X[nxt]) + abs(Y[cur] - Y[nxt]); double addtime = T * d + W[nxt]; dp[i + (1 << nxt)][nxt] = min(dp[i + (1 << nxt)][nxt], dp[i][cur] + addtime); } } } } } double ans = INF; for (int last = 1; last < N; last++) { double T = double(100) / double(120); double d = abs(X[last] - X[0]) + abs(Y[last] - Y[0]); ans = min(ans, dp[(1 << N) - 1][last] + T * d); //cout << last << " : " << dp[(1 << N) - 1][last] << endl; } cout << setprecision(15) << ans << endl; return 0; }