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

提出ソース

結果

問題	No.1599 Hikyaku
ユーザー	e869120
提出日時	2021-05-03 18:07:21
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	2,260 ms / 7,500 ms
コード長	3,791 bytes
コンパイル時間	933 ms
コンパイル使用メモリ	92,900 KB
実行使用メモリ	63,804 KB
最終ジャッジ日時	2023-09-14 06:44:52
合計ジャッジ時間	50,605 ms
ジャッジサーバーID （参考情報）	judge12 / judge13

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	142 ms 59,176 KB
testcase_01	AC	204 ms 60,088 KB
testcase_02	AC	208 ms 60,112 KB
testcase_03	AC	148 ms 59,308 KB
testcase_04	AC	1,684 ms 61,580 KB
testcase_05	AC	559 ms 60,016 KB
testcase_06	AC	1,420 ms 61,860 KB
testcase_07	AC	411 ms 60,204 KB
testcase_08	AC	1,600 ms 61,644 KB
testcase_09	AC	185 ms 59,352 KB
testcase_10	AC	323 ms 59,652 KB
testcase_11	AC	166 ms 59,200 KB
testcase_12	AC	389 ms 60,744 KB
testcase_13	AC	322 ms 60,792 KB
testcase_14	AC	124 ms 59,176 KB
testcase_15	AC	147 ms 59,196 KB
testcase_16	AC	507 ms 59,996 KB
testcase_17	AC	1,657 ms 61,456 KB
testcase_18	AC	1,690 ms 61,672 KB
testcase_19	AC	2,249 ms 63,096 KB
testcase_20	AC	2,260 ms 62,868 KB
testcase_21	AC	2,079 ms 62,976 KB
testcase_22	AC	2,060 ms 63,084 KB
testcase_23	AC	2,017 ms 63,004 KB
testcase_24	AC	2,017 ms 63,188 KB
testcase_25	AC	1,903 ms 63,804 KB
testcase_26	AC	1,547 ms 62,184 KB
testcase_27	AC	836 ms 61,232 KB
testcase_28	AC	840 ms 60,716 KB
testcase_29	AC	549 ms 60,584 KB
testcase_30	AC	325 ms 59,648 KB
testcase_31	AC	142 ms 59,232 KB
testcase_32	AC	142 ms 59,204 KB
testcase_33	AC	142 ms 59,204 KB
testcase_34	AC	728 ms 60,340 KB
testcase_35	AC	1,134 ms 61,116 KB
testcase_36	AC	1,672 ms 61,980 KB
testcase_37	AC	1,691 ms 61,696 KB
testcase_38	AC	1,694 ms 61,720 KB
testcase_39	AC	1,705 ms 61,556 KB
testcase_40	AC	1,754 ms 61,696 KB
testcase_41	AC	110 ms 59,316 KB
testcase_42	AC	143 ms 59,192 KB
testcase_43	AC	110 ms 59,320 KB
testcase_44	AC	529 ms 59,956 KB
testcase_45	AC	528 ms 60,180 KB
testcase_46	AC	747 ms 60,436 KB
testcase_47	AC	745 ms 60,320 KB
testcase_48	AC	1,578 ms 61,428 KB
testcase_49	AC	144 ms 59,232 KB
testcase_50	AC	324 ms 59,548 KB
testcase_51	AC	524 ms 59,984 KB
testcase_52	AC	361 ms 60,376 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];
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;
}

yukicoder

結果

テストケース

ソースコード