#653761 (C++14) No.1599 Hikyaku

提出ソース

結果

問題	No.1599 Hikyaku
ユーザー	e869120
提出日時	2021-05-03 18:00:47
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	1,661 ms / 7,500 ms
コード長	3,708 bytes
コンパイル時間	1,094 ms
コンパイル使用メモリ	91,808 KB
実行使用メモリ	38,932 KB
最終ジャッジ日時	2024-07-01 14:11:36
合計ジャッジ時間	40,710 ms
ジャッジサーバーID （参考情報）	judge1 / judge4

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	111 ms 34,176 KB
testcase_01	AC	181 ms 36,088 KB
testcase_02	AC	182 ms 36,212 KB
testcase_03	AC	116 ms 34,176 KB
testcase_04	AC	1,249 ms 37,632 KB
testcase_05	AC	432 ms 36,096 KB
testcase_06	AC	1,059 ms 37,880 KB
testcase_07	AC	345 ms 36,196 KB
testcase_08	AC	1,154 ms 37,760 KB
testcase_09	AC	171 ms 34,304 KB
testcase_10	AC	262 ms 34,688 KB
testcase_11	AC	148 ms 34,048 KB
testcase_12	AC	314 ms 35,512 KB
testcase_13	AC	254 ms 35,508 KB
testcase_14	AC	106 ms 34,176 KB
testcase_15	AC	129 ms 34,176 KB
testcase_16	AC	415 ms 34,816 KB
testcase_17	AC	1,302 ms 37,504 KB
testcase_18	AC	1,314 ms 37,632 KB
testcase_19	AC	1,661 ms 38,904 KB
testcase_20	AC	1,651 ms 38,932 KB
testcase_21	AC	1,645 ms 37,676 KB
testcase_22	AC	1,611 ms 37,904 KB
testcase_23	AC	1,578 ms 37,644 KB
testcase_24	AC	1,611 ms 37,548 KB
testcase_25	AC	1,479 ms 37,852 KB
testcase_26	AC	1,207 ms 36,876 KB
testcase_27	AC	676 ms 36,076 KB
testcase_28	AC	701 ms 35,704 KB
testcase_29	AC	443 ms 35,456 KB
testcase_30	AC	265 ms 34,688 KB
testcase_31	AC	130 ms 34,176 KB
testcase_32	AC	128 ms 34,048 KB
testcase_33	AC	128 ms 34,176 KB
testcase_34	AC	586 ms 35,408 KB
testcase_35	AC	906 ms 35,848 KB
testcase_36	AC	1,320 ms 36,516 KB
testcase_37	AC	1,340 ms 36,556 KB
testcase_38	AC	1,345 ms 36,500 KB
testcase_39	AC	1,371 ms 37,048 KB
testcase_40	AC	1,404 ms 37,612 KB
testcase_41	AC	92 ms 34,048 KB
testcase_42	AC	129 ms 34,048 KB
testcase_43	AC	92 ms 34,176 KB
testcase_44	AC	430 ms 35,072 KB
testcase_45	AC	430 ms 34,944 KB
testcase_46	AC	604 ms 35,200 KB
testcase_47	AC	608 ms 35,328 KB
testcase_48	AC	1,266 ms 36,352 KB
testcase_49	AC	130 ms 34,048 KB
testcase_50	AC	272 ms 34,560 KB
testcase_51	AC	430 ms 34,816 KB
testcase_52	AC	301 ms 35,012 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#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];
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<double, int, int, int>, vector<tuple<double, int, int, int>>, greater<tuple<double, int, int, int>>> 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;
}

yukicoder

結果

テストケース

ソースコード