#include #include #include #include #include #include using namespace std; typedef long long ll; #define rep(i,n) for(int i=0;i<(n);i++) const int INF = 1e9; int x[20], y[20]; double w[20]; int dist[20][20]; //dp[mask][i] := mask集合を巡って、iにいるときの最小コスト double dp[(1 << 20)][20]; //weight[maks] := mask集合の時の荷物の重さ double weight[(1 << 20)]; int main(void){ cin >> x[0] >> y[0]; w[0] = 0; int n; cin >> n; for (int i = 1; i <= n; ++i) { cin >> x[i] >> y[i] >> w[i]; } rep(i, n + 1)rep(j, n + 1){ int len = abs(x[i] - x[j]) + abs(y[i] - y[j]); dist[i][j] = len; } //前計算 for (int mask = 0; mask < (1 << (n + 1)); ++mask) { double tmp = 0; for (int i = 0; i < n + 1; ++i) { if((mask & (1 << i)) == 0){ tmp += w[i]; } weight[mask] = tmp; } } rep(i, (1 << 20))rep(j, 20) dp[i][j] = INF; dp[0][0] = 0; for (int mask = 0; mask < (1 << (n + 1)); ++mask) { for (int i = 0; i < n + 1; ++i)//現在時点 { for (int p = 0; p < n + 1; ++p)//次に行くところ { if((mask & (1 << p)) == 0){//pをまだ訪れていない double cost = dist[i][p] * (double)((w[i] + 100.0) / 120.0); // printf("cost %f\n", cost); dp[mask | (1 << p)][p] = min(dp[mask | (1 << p)][p], dp[mask][i] + cost); } } } } double ret = 0; for (int i = 0; i < n + 1; ++i){ ret += w[i]; } // printf("ret %f\n", ret); // printf("dp %f\n", dp[(1 << (n + 1)) - 1][0]); printf("%.9f\n", dp[(1 << (n + 1)) - 1][0] + ret); return 0; }