#673244 (C) No.1599 Hikyaku

提出ソース
結果

問題	No.1599 Hikyaku
ユーザー	👑 ygussany
提出日時	2021-07-06 11:08:16
言語	C (gcc 13.3.0)
結果	AC
実行時間	1,629 ms / 7,500 ms
コード長	6,268 bytes
コンパイル時間	485 ms
コンパイル使用メモリ	40,192 KB
実行使用メモリ	87,032 KB
最終ジャッジ日時	2024-07-01 14:30:01
合計ジャッジ時間	39,513 ms
ジャッジサーバーID （参考情報）	judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン	結果
sample	AC * 4
other	AC * 49
権限があれば一括ダウンロードができます
ソースコード

raw source code
#include <stdio.h>
#include <math.h>

const double eps = 1e-9, sup = 1e+9;

typedef struct List {
	struct List *next;
	int v;
	double cost;
} list;

typedef struct {
	double key;
	int id;
} data;
 
typedef struct {
	data obj[4000001];
	int size;
} min_heap;
 
void push(data x, min_heap* h)
{
	int i = ++(h->size), j = i >> 1;
	data tmp;
	h->obj[i] = x;
	while (j > 0) {
		if (h->obj[i].key < h->obj[j].key) {
			tmp = h->obj[j];
			h->obj[j] = h->obj[i];
			h->obj[i] = tmp;
			i = j;
			j >>= 1;
		} else break;
	}
}

data pop(min_heap* h)
{
	int i = 1, j = 2;
	data output = h->obj[1], tmp;
	h->obj[1] = h->obj[(h->size)--];
	while (j <= h->size) {
		if (j < h->size && h->obj[j^1].key < h->obj[j].key) j ^= 1;
		if (h->obj[j].key < h->obj[i].key) {
			tmp = h->obj[j];
			h->obj[j] = h->obj[i];
			h->obj[i] = tmp;
			i = j;
			j = i << 1;
		} else break;
	}
	return output;
}

void chmin(double* a, double b)
{
	if (*a > b) *a = b;
}

int main()
{
	int i, N, X, Y, x[100001], y[100001], v[100001];
	scanf("%d %d", &X, &Y);
	scanf("%d", &N);
	for (i = 1; i <= N; i++) scanf("%d %d %d", &(x[i]), &(y[i]), &(v[i]));
	
	int j, k, n = 360000, m, u, w;
	list *adj[1000001] = {}, e[4000001], *p;
	for (i = 1, m = 0; i <= 600; i++) {
		for (j = 1; j <= 600; j++) {
			u = (i - 1) * 600 + j;
			if (i < 600) {
				w = u + 600;
				e[m].v = w;
				e[m+1].v = u;
				e[m].cost = 1000.0;
				e[m+1].cost = 1000.0;
				e[m].next = adj[u];
				e[m+1].next = adj[w];
				adj[u] = &(e[m]);
				adj[w] = &(e[m+1]);
				m += 2;
			}
			if (j < 600) {
				w = u + 1;
				e[m].v = w;
				e[m+1].v = u;
				e[m].cost = 1000.0;
				e[m+1].cost = 1000.0;
				e[m].next = adj[u];
				e[m+1].next = adj[w];
				adj[u] = &(e[m]);
				adj[w] = &(e[m+1]);
				m += 2;
			}
		}
	}
	
	double dist[8][1000001];
	min_heap h;
	data d;
	for (u = 1; u <= n; u++) dist[v[1]][u] = sup;
	h.size = 0;
	u = (x[1] - 1) * 600 + y[1];
	dist[v[1]][u] = 0.0;
	d.key = 0.0;
	d.id = u;
	push(d, &h);
	while (h.size > 0) {
		d = pop(&h);
		u = d.id;
		if (fabs(d.key - dist[v[1]][u]) > eps) continue;
		for (p = adj[u]; p != NULL; p = p->next) {
			w = p->v;
			if (dist[v[1]][w] - dist[v[1]][u] - p->cost / v[1] > eps) {
				dist[v[1]][w] = dist[v[1]][u] + p->cost / v[1];
				d.key = dist[v[1]][w];
				d.id = w;
				push(d, &h);
			}
		}
	}
	for (k = v[1] + 1; k <= 7; k++) {
		for (u = 1; u <= n; u++) dist[k][u] = sup;
		h.size = 0;
		for (i = 1; i <= N; i++) {
			if (v[i] != k) continue;
			u = (x[i] - 1) * 600 + y[i];
			dist[k][u] = 0.0;
			d.key = 0.0;
			d.id = u;
			push(d, &h);
		}
		while (h.size > 0) {
			d = pop(&h);
			u = d.id;
			if (fabs(d.key - dist[k][u]) > eps) continue;
			for (p = adj[u]; p != NULL; p = p->next) {
				w = p->v;
				if (dist[k][w] - dist[k][u] - p->cost / k > eps) {
					dist[k][w] = dist[k][u] + p->cost / k;
					d.key = dist[k][w];
					d.id = w;
					push(d, &h);
				}
			}
		}
	}
	
	int l;
	double a, b, aux_dist[8][1000001];
	for (u = 1; u <= n; u++) aux_dist[v[1]][u] = dist[v[1]][u];
	for (k = v[1] + 1; k <= 7; k++) {
		for (u = 1; u <= n; u++) aux_dist[k][u] = sup;
		if (dist[k][1] == sup) continue;
		h.size = 0;
		for (j = v[1]; j < k; j++) {
			if (aux_dist[j][1] == sup) continue;
			for (i = m - 2; i >= 0; i -= 2) {
				u = e[i].v;
				w = e[i+1].v;
				if (u == 0) continue;
				if (fabs(dist[k][u] - aux_dist[j][u]) < eps) {
					if (aux_dist[k][u] - dist[k][u] > eps) {
						aux_dist[k][u] = dist[k][u];
						d.key = aux_dist[k][u];
						d.id = u;
						push(d, &h);
					}
				}
				if (fabs(dist[k][w] - aux_dist[j][w]) < eps) {
					if (aux_dist[k][w] - dist[k][w] > eps) {
						aux_dist[k][w] = dist[k][w];
						d.key = aux_dist[k][w];
						d.id = w;
						push(d, &h);
					}
				}
				if (aux_dist[j][u] - dist[k][u] > eps && dist[k][w] - aux_dist[j][w] > eps) {
					e[i].v = 0;
					e[i+1].v = 0;
					a = -(dist[k][u] - aux_dist[j][w] - e[i].cost / j) / (1.0 / j + 1.0 / k);
					b = e[i].cost - a;
					e[m].v = ++n;
					e[m+1].v = u;
					e[m].cost = a;
					e[m+1].cost = a;
					e[m].next = adj[u];
					e[m+1].next = adj[n];
					adj[u] = &(e[m]);
					adj[n] = &(e[m+1]);
					m += 2;
					e[m].v = n;
					e[m+1].v = w;
					e[m].cost = b;
					e[m+1].cost = b;
					e[m].next = adj[w];
					e[m+1].next = adj[n];
					adj[w] = &(e[m]);
					adj[n] = &(e[m+1]);
					m += 2;
					for (l = v[1]; l <= 7; l++) {
						dist[l][n] = dist[l][u] + a / l;
						chmin(&(dist[l][n]), dist[l][w] + b / l);
					}
					for (l = v[1]; l < k; l++) {
						aux_dist[l][n] = aux_dist[l][u] + a / l;
						chmin(&(aux_dist[l][n]), aux_dist[l][w] + b / l);
					}
					aux_dist[k][n] = dist[k][u] + a / k;
					d.key = aux_dist[k][n];
					d.id = n;
					push(d, &h);
				} else if (aux_dist[j][w] - dist[k][w] > eps && dist[k][u] - aux_dist[j][u] > eps) {
					e[i].v = 0;
					e[i+1].v = 0;
					a = -(dist[k][w] - aux_dist[j][u] - e[i].cost / j) / (1.0 / j + 1.0 / k);
					b = e[i].cost - a;
					e[m].v = ++n;
					e[m+1].v = w;
					e[m].cost = a;
					e[m+1].cost = a;
					e[m].next = adj[w];
					e[m+1].next = adj[n];
					adj[w] = &(e[m]);
					adj[n] = &(e[m+1]);
					m += 2;
					e[m].v = n;
					e[m+1].v = u;
					e[m].cost = b;
					e[m+1].cost = b;
					e[m].next = adj[u];
					e[m+1].next = adj[n];
					adj[u] = &(e[m]);
					adj[n] = &(e[m+1]);
					m += 2;
					for (l = v[1]; l <= 7; l++) {
						dist[l][n] = dist[l][w] + a / l;
						chmin(&(dist[l][n]), dist[l][u] + b / l);
					}
					for (l = v[1]; l < k; l++) {
						aux_dist[l][n] = aux_dist[l][w] + a / l;
						chmin(&(aux_dist[l][n]), aux_dist[l][u] + b / l);
					}
					aux_dist[k][n] = dist[k][w] + a / k;
					d.key = aux_dist[k][n];
					d.id = n;
					push(d, &h);
				}
			}
		}
		
		while (h.size > 0) {
			d = pop(&h);
			u = d.id;
			if (fabs(d.key - aux_dist[k][u]) > eps) continue;
			for (p = adj[u]; p != NULL; p = p->next) {
				w = p->v;
				if (w == 0) continue;
				if (aux_dist[k][w] - aux_dist[k][u] - p->cost / k > eps) {
					aux_dist[k][w] = aux_dist[k][u] + p->cost / k;
					d.key = aux_dist[k][w];
					d.id = w;
					push(d, &h);
				}
			}
		}
	}
	
	double ans = sup;
	u = (X - 1) * 600 + Y;
	for (k = v[1]; k <= 7; k++) if (ans > aux_dist[k][u]) ans = aux_dist[k][u];
	printf("%.8f\n", ans);
	fflush(stdout);
	return 0;
}
yukicoder

結果

ソースコード
