結果

問題 No.1599 Hikyaku
ユーザー e869120e869120
提出日時 2021-05-03 18:07:21
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 2,337 ms / 7,500 ms
コード長 3,791 bytes
コンパイル時間 963 ms
コンパイル使用メモリ 92,904 KB
実行使用メモリ 59,268 KB
最終ジャッジ日時 2024-07-01 14:13:18
合計ジャッジ時間 52,465 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 153 ms
54,016 KB
testcase_01 AC 220 ms
56,188 KB
testcase_02 AC 224 ms
56,064 KB
testcase_03 AC 158 ms
54,144 KB
testcase_04 AC 1,730 ms
57,600 KB
testcase_05 AC 583 ms
56,320 KB
testcase_06 AC 1,474 ms
57,728 KB
testcase_07 AC 437 ms
56,304 KB
testcase_08 AC 1,522 ms
57,856 KB
testcase_09 AC 205 ms
54,400 KB
testcase_10 AC 342 ms
54,656 KB
testcase_11 AC 194 ms
54,144 KB
testcase_12 AC 404 ms
55,744 KB
testcase_13 AC 338 ms
55,864 KB
testcase_14 AC 138 ms
54,144 KB
testcase_15 AC 159 ms
54,144 KB
testcase_16 AC 538 ms
54,912 KB
testcase_17 AC 1,731 ms
57,600 KB
testcase_18 AC 1,771 ms
57,728 KB
testcase_19 AC 2,337 ms
59,268 KB
testcase_20 AC 2,274 ms
59,172 KB
testcase_21 AC 2,138 ms
58,172 KB
testcase_22 AC 2,141 ms
58,264 KB
testcase_23 AC 2,119 ms
58,136 KB
testcase_24 AC 2,137 ms
58,152 KB
testcase_25 AC 1,996 ms
58,472 KB
testcase_26 AC 1,644 ms
57,232 KB
testcase_27 AC 869 ms
56,260 KB
testcase_28 AC 922 ms
55,804 KB
testcase_29 AC 614 ms
55,688 KB
testcase_30 AC 340 ms
54,784 KB
testcase_31 AC 154 ms
54,144 KB
testcase_32 AC 153 ms
54,144 KB
testcase_33 AC 156 ms
54,144 KB
testcase_34 AC 769 ms
55,388 KB
testcase_35 AC 1,196 ms
56,084 KB
testcase_36 AC 1,747 ms
56,748 KB
testcase_37 AC 1,783 ms
56,784 KB
testcase_38 AC 1,779 ms
56,848 KB
testcase_39 AC 1,800 ms
57,148 KB
testcase_40 AC 1,856 ms
57,724 KB
testcase_41 AC 121 ms
54,016 KB
testcase_42 AC 154 ms
54,144 KB
testcase_43 AC 124 ms
54,016 KB
testcase_44 AC 556 ms
54,784 KB
testcase_45 AC 553 ms
54,912 KB
testcase_46 AC 788 ms
55,168 KB
testcase_47 AC 795 ms
55,296 KB
testcase_48 AC 1,688 ms
56,448 KB
testcase_49 AC 153 ms
54,144 KB
testcase_50 AC 340 ms
54,528 KB
testcase_51 AC 553 ms
54,784 KB
testcase_52 AC 383 ms
55,372 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <queue>
#include <tuple>
#include <vector>
#include <algorithm>
#include <functional>
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];
long 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<pair<int, int>> 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<tuple<long double, int, int, int>, vector<tuple<long double, int, int, int>>, greater<tuple<long double, int, int, int>>> Q;
	dist[V[1]][X[1]][Y[1]] = 0.0L;
	Q.push(make_tuple(0.0, V[1], X[1], Y[1]));

	while (!Q.empty()) {
		long 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.0L / pos1) {
				dist[pos1][ux][uy] = cur + 1000.0L / 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;
			long double I = max(cur, 1000.0L * 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;

			long double ret = cur, retx = 0.0L; int preidx = pos1;
			while (true) {
				long 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;
					long double p1 = retx;
					long double p2 = 1000.0L - 1.0L * (ret - 1000.0L * dp[j][ux][uy] / j) * j;
					long double tm = ret + 1.0L * (p2 - p1) / (preidx + j);
					long double za = p1 + 1.0L * preidx * (p2 - p1) / (preidx + j);
					if (minx > tm && za <= 1000.0L) {
						minx = tm;
						zahyou = za;
						idx = j;
					}
				}
				if (idx == -1) break;
				long double goal = minx + 1.0L * (1000.0L - 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. 出力
	long double FinalAns = 1e9;
	for (int i = 1; i <= Max_V; i++) FinalAns = min(FinalAns, dist[i][S][T]);
	printf("%.12Lf\n", FinalAns);
	return 0;
}
0