結果

問題 No.1599 Hikyaku
ユーザー e869120e869120
提出日時 2021-05-03 18:00:47
言語 C++14
(gcc 13.3.0 + boost 1.87.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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 49
権限があれば一括ダウンロードができます

ソースコード

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];
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;
}
0