#include #include #include #include #include #include using namespace std; // 入力 int Max_HW = 600; int Max_V = 7; int N, S, T, X[1 << 18], Y[1 << 18], V[1 << 18]; // その他の変数 int dx[4] = { 0, 1, 0, -1 }; int dy[4] = { 1, 0, -1, 0 }; int dp[8][609][609]; double dist[8][609][609]; bool used[8][609][609]; int main() { // Step #1. 入力 cin >> S >> T; cin >> N; for (int i = 1; i <= N; i++) cin >> X[i] >> Y[i] >> V[i]; // Step #2. 初期化 for (int i = 1; i <= Max_HW; i++) { for (int j = 1; j <= Max_HW; j++) { for (int k = 1; k <= Max_V; k++) dp[k][i][j] = (1 << 20); for (int k = 1; k <= Max_V; k++) dist[k][i][j] = 1e9; } } // Step #3. 多始点最短路(幅優先探索) for (int i = 1; i <= Max_V; i++) { queue> QQ; for (int j = 1; j <= N; j++) { if (V[j] != i) continue; dp[i][X[j]][Y[j]] = 0; QQ.push(make_pair(X[j], Y[j])); } while (!QQ.empty()) { int px = QQ.front().first; int py = QQ.front().second; QQ.pop(); for (int j = 0; j < 4; j++) { int sx = px + dx[j], sy = py + dy[j]; if (sx <= 0 || sy <= 0 || sx > Max_HW || sy > Max_HW) continue; if (dp[i][sx][sy] > dp[i][px][py] + 1) { dp[i][sx][sy] = dp[i][px][py] + 1; QQ.push(make_pair(sx, sy)); } } } } // Step #4. ダイクストラ法 priority_queue, vector>, greater>> Q; dist[V[1]][X[1]][Y[1]] = 0.0; Q.push(make_tuple(0.0, V[1], X[1], Y[1])); while (!Q.empty()) { double cur = get<0>(Q.top()); int pos1 = get<1>(Q.top()); int pos2 = get<2>(Q.top()); int pos3 = get<3>(Q.top()); Q.pop(); if (used[pos1][pos2][pos3] == true) continue; used[pos1][pos2][pos3] = true; // 移動パターン 1: 隣接 4 方向への移動 for (int i = 0; i < 4; i++) { int ux = pos2 + dx[i]; int uy = pos3 + dy[i]; if (ux <= 0 || uy <= 0 || ux > Max_HW || uy > Max_HW) continue; if (dist[pos1][ux][uy] > cur + 1000.0 / pos1) { dist[pos1][ux][uy] = cur + 1000.0 / pos1; Q.push(make_tuple(dist[pos1][ux][uy], pos1, ux, uy)); } } // 移動パターン 2: 今いる頂点で待つ for (int i = pos1 + 1; i <= Max_V; i++) { if (dp[i][pos2][pos3] == (1 << 20)) continue; double I = max(cur, 1000.0 * dp[i][pos2][pos3] / i); if (dist[i][pos2][pos3] > I) { dist[i][pos2][pos3] = I; Q.push(make_tuple(dist[i][pos2][pos3], i, pos2, pos3)); } } // 移動パターン 3: 辺の途中で速度を上げる for (int i = 0; i < 4; i++) { int ux = pos2 + dx[i]; int uy = pos3 + dy[i]; if (ux <= 0 || uy <= 0 || ux > Max_HW || uy > Max_HW) continue; double ret = cur, retx = 0.0; int preidx = pos1; while (true) { double minx = 1e9, zahyou = 0; int idx = -1; for (int j = preidx + 1; j <= Max_V; j++) { if (dp[j][ux][uy] == (1 << 20)) continue; double p1 = retx; double p2 = 1000.0 - 1.0 * (ret - 1000.0 * dp[j][ux][uy] / j) * j; double tm = ret + 1.0 * (p2 - p1) / (preidx + j); double za = p1 + 1.0 * preidx * (p2 - p1) / (preidx + j); if (minx > tm && za <= 1000.0) { minx = tm; zahyou = za; idx = j; } } if (idx == -1) break; double goal = minx + 1.0 * (1000.0 - zahyou) / idx; if (dist[idx][ux][uy] > goal) { dist[idx][ux][uy] = goal; Q.push(make_tuple(dist[idx][ux][uy], idx, ux, uy)); } ret = minx; retx = zahyou; preidx = idx; } } } // Step #5. 出力 double FinalAns = 1e9; for (int i = 1; i <= Max_V; i++) FinalAns = min(FinalAns, dist[i][S][T]); printf("%.12lf\n", FinalAns); return 0; }