結果

問題 No.1599 Hikyaku
コンテスト
ユーザー olphe
提出日時 2021-07-09 23:41:30
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 2,862 bytes
コンパイル時間 1,356 ms
コンパイル使用メモリ 125,976 KB
実行使用メモリ 487,640 KB
最終ジャッジ日時 2024-07-01 18:33:06
合計ジャッジ時間 27,317 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 4
other AC * 6 TLE * 1 -- * 42
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include "iostream"
#include "climits"
#include "list"
#include "queue"
#include "stack"
#include "set"
#include "functional"
#include "algorithm"
#include "string"
#include "map"
#include "unordered_map"
#include "unordered_set"
#include "iomanip"
#include "cmath"
#include "random"
#include "bitset"
#include "cstdio"
#include "numeric"
#include "cassert"
#include "ctime"

using namespace std;

constexpr long long int MOD = 1000000007;
//constexpr int MOD = 1000000007;
//constexpr int MOD = 998244353;
//constexpr long long int MOD = 998244353;
constexpr double EPS = 1e-8;

//int N, M, K, T, H, W, L, R;
long long int N, M, K, T, H, W, L, R;

struct Node {
	int y, x, v, ok;
	long double cost;
	Node(int y, int x, int v, int ok,long double cost) :y(y), x(x), v(v), ok(ok),cost(cost) {

	}
	bool operator<(const Node& n)const {
		return cost > n.cost;
	}
};

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);

	H = 600, W = 600;
	int gy, gx;
	cin >> gy >> gx;
	gy--, gx--;
	cin >> N;
	vector<vector<vector<vector<long double>>>>dis(H, vector<vector<vector<long double>>>(W, vector<vector<long double>>(8, vector<long double>(2, MOD))));
	priority_queue<Node>PQ;
	int exist[8] = {};
	for (int i = 0; i < N; i++) {
		int y, x, v;
		cin >> y >> x >> v;
		exist[v] = 1;
		y--, x--;
		if (i) {
			dis[y][x][v][0] = 0;
			PQ.push(Node(y, x, v, 0, 0));
		}
		else {
			dis[y][x][v][1] = 0;
			PQ.push(Node(y, x, v, 1, 0));
		}
	}
	int dir[] = { 1,0,-1,0,1 };
	while (!PQ.empty()) {
		auto box = PQ.top();
		PQ.pop();
		if (box.ok) {
			for (int i = 1; i < 8; i++) {
				if (!exist[i])continue;
				if (dis[box.y][box.x][i][1] > dis[box.y][box.x][i][0] && dis[box.y][box.x][i][0] > box.cost) {
					dis[box.y][box.x][i][1] = dis[box.y][box.x][i][0];
					PQ.push(Node(box.y, box.x, i, 1, dis[box.y][box.x][i][0]));
				}
			}
		}
		else {
			for (int i = 1; i < 8; i++) {
				if (!exist[i])continue;
				if (dis[box.y][box.x][i][1] > box.cost) {
					long double d = box.cost + (dis[box.y][box.x][i][1] - box.cost) * i / (i + box.v) * 2;
					if (dis[box.y][box.x][box.v][1] > d) {
						PQ.push(Node(box.y, box.x, box.v, 1, d));
					}
				}
				if (dis[box.y][box.x][i][1] <= box.cost) {
					if (dis[box.y][box.x][box.v][1] > box.cost) {
						PQ.push(Node(box.y, box.x, box.v, 1, box.cost));
					}
				}
			}
		}
		for (int d = 0; d < 4; d++) {
			int ny = box.y + dir[d];
			int nx = box.x + dir[d + 1];
			if (ny < 0 || nx < 0 || ny >= H || nx >= W)continue;
			if (dis[ny][nx][box.v][box.ok] > box.cost + ((long double)1000) / box.v) {
				dis[ny][nx][box.v][box.ok] = box.cost + ((long double)1000) / box.v;
				PQ.push(Node(ny, nx, box.v, box.ok, box.cost + ((long double)1000) / box.v));
			}
		}
	}
	long double ans = MOD;
	for (int i = 1; i <= 7; i++) {
		ans = min(ans, dis[gy][gx][i][1]);
	}
	cout << fixed << setprecision(20) << ans << endl;
}
0