#include #include using namespace std; #define FOR(i, a, n) for(int i=a; i=a; i--) #define REP(i, n) FOR(i, 0, n) #define RREP(i, n) FOR(i, 0, n) #define INF 10000000 double dp[(1 << 14)][14]; int main() { int X[14], Y[14], N; double W[14], sumW = 0.0; cin >> X[0] >> Y[0] >> N; W[0] = 0.0; REP(i, N) { cin >> X[i + 1] >> Y[i + 1] >> W[i + 1]; sumW += W[i + 1]; } N++; REP(i, 1 << N) REP(j, N) dp[i][j] = INF; dp[0][0] = 0; REP(mask, 1 << N) { REP(i, N) { double sw = sumW; REP(j, N) if (mask&(1 << j)) sw -= W[j]; REP(j, N) { if (mask&(1 << j)) continue; int md = abs(X[j] - X[i]) + abs(Y[j] - Y[i]); dp[mask | (1 << j)][j] = min(dp[mask | (1 << j)][j], dp[mask][i] + (md*(sw + 100.0) / 120.0) + W[j]); } } } cout << dp[(1 << N) - 1][0] << endl; return 0; }