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

提出ソース

結果

問題	No.1599 Hikyaku
ユーザー	e869120
提出日時	2021-05-03 18:00:47
言語	C++14 (gcc 13.2.0 + boost 1.83.0)
結果	AC
実行時間	1,601 ms / 7,500 ms
コード長	3,708 bytes
コンパイル時間	1,299 ms
コンパイル使用メモリ	91,880 KB
実行使用メモリ	42,644 KB
最終ジャッジ日時	2023-09-14 06:43:15
合計ジャッジ時間	38,367 ms
ジャッジサーバーID （参考情報）	judge15 / judge14

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	107 ms 38,912 KB
testcase_01	AC	168 ms 40,316 KB
testcase_02	AC	170 ms 40,252 KB
testcase_03	AC	109 ms 38,844 KB
testcase_04	AC	1,207 ms 41,572 KB
testcase_05	AC	411 ms 40,036 KB
testcase_06	AC	1,033 ms 41,940 KB
testcase_07	AC	327 ms 40,484 KB
testcase_08	AC	1,103 ms 41,828 KB
testcase_09	AC	151 ms 38,988 KB
testcase_10	AC	238 ms 39,272 KB
testcase_11	AC	130 ms 38,764 KB
testcase_12	AC	288 ms 39,780 KB
testcase_13	AC	232 ms 39,824 KB
testcase_14	AC	90 ms 38,716 KB
testcase_15	AC	109 ms 38,892 KB
testcase_16	AC	369 ms 39,448 KB
testcase_17	AC	1,206 ms 41,580 KB
testcase_18	AC	1,226 ms 41,632 KB
testcase_19	AC	1,551 ms 42,644 KB
testcase_20	AC	1,552 ms 42,508 KB
testcase_21	AC	1,498 ms 42,016 KB
testcase_22	AC	1,601 ms 42,088 KB
testcase_23	AC	1,481 ms 42,004 KB
testcase_24	AC	1,481 ms 42,048 KB
testcase_25	AC	1,382 ms 42,164 KB
testcase_26	AC	1,121 ms 41,420 KB
testcase_27	AC	601 ms 40,432 KB
testcase_28	AC	631 ms 40,204 KB
testcase_29	AC	399 ms 39,784 KB
testcase_30	AC	233 ms 39,204 KB
testcase_31	AC	107 ms 38,696 KB
testcase_32	AC	106 ms 38,920 KB
testcase_33	AC	106 ms 38,768 KB
testcase_34	AC	530 ms 39,984 KB
testcase_35	AC	820 ms 40,228 KB
testcase_36	AC	1,203 ms 41,124 KB
testcase_37	AC	1,212 ms 41,016 KB
testcase_38	AC	1,218 ms 40,972 KB
testcase_39	AC	1,228 ms 41,204 KB
testcase_40	AC	1,265 ms 41,584 KB
testcase_41	AC	75 ms 38,856 KB
testcase_42	AC	107 ms 38,788 KB
testcase_43	AC	76 ms 38,892 KB
testcase_44	AC	384 ms 39,524 KB
testcase_45	AC	384 ms 39,520 KB
testcase_46	AC	540 ms 39,764 KB
testcase_47	AC	544 ms 39,796 KB
testcase_48	AC	1,140 ms 40,888 KB
testcase_49	AC	106 ms 38,848 KB
testcase_50	AC	240 ms 39,152 KB
testcase_51	AC	381 ms 39,544 KB
testcase_52	AC	272 ms 39,368 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

結果

テストケース

ソースコード