#673244 (C) No.1599 Hikyaku

提出ソース

結果

問題	No.1599 Hikyaku
ユーザー	👑 ygussany
提出日時	2021-07-06 11:08:16
言語	C (gcc 12.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

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	135 ms 82,944 KB
testcase_01	AC	161 ms 83,944 KB
testcase_02	AC	169 ms 83,964 KB
testcase_03	AC	118 ms 60,208 KB
testcase_04	AC	1,199 ms 84,172 KB
testcase_05	AC	475 ms 61,696 KB
testcase_06	AC	1,536 ms 79,872 KB
testcase_07	AC	408 ms 57,344 KB
testcase_08	AC	1,629 ms 79,872 KB
testcase_09	AC	123 ms 49,120 KB
testcase_10	AC	355 ms 54,784 KB
testcase_11	AC	128 ms 49,024 KB
testcase_12	AC	315 ms 60,416 KB
testcase_13	AC	303 ms 71,548 KB
testcase_14	AC	116 ms 49,024 KB
testcase_15	AC	138 ms 82,816 KB
testcase_16	AC	457 ms 82,816 KB
testcase_17	AC	1,202 ms 84,212 KB
testcase_18	AC	1,211 ms 84,632 KB
testcase_19	AC	1,480 ms 87,032 KB
testcase_20	AC	1,469 ms 87,032 KB
testcase_21	AC	1,491 ms 84,916 KB
testcase_22	AC	1,475 ms 84,848 KB
testcase_23	AC	1,349 ms 84,292 KB
testcase_24	AC	1,359 ms 84,352 KB
testcase_25	AC	1,286 ms 84,096 KB
testcase_26	AC	1,087 ms 83,712 KB
testcase_27	AC	654 ms 83,200 KB
testcase_28	AC	652 ms 83,328 KB
testcase_29	AC	469 ms 82,944 KB
testcase_30	AC	300 ms 82,816 KB
testcase_31	AC	134 ms 82,816 KB
testcase_32	AC	134 ms 82,796 KB
testcase_33	AC	133 ms 82,792 KB
testcase_34	AC	665 ms 83,072 KB
testcase_35	AC	869 ms 83,328 KB
testcase_36	AC	1,266 ms 83,584 KB
testcase_37	AC	1,243 ms 83,712 KB
testcase_38	AC	1,192 ms 83,584 KB
testcase_39	AC	1,179 ms 84,096 KB
testcase_40	AC	1,197 ms 84,984 KB
testcase_41	AC	111 ms 49,144 KB
testcase_42	AC	134 ms 82,816 KB
testcase_43	AC	110 ms 49,024 KB
testcase_44	AC	459 ms 82,816 KB
testcase_45	AC	458 ms 82,816 KB
testcase_46	AC	627 ms 82,776 KB
testcase_47	AC	628 ms 82,784 KB
testcase_48	AC	1,175 ms 82,816 KB
testcase_49	AC	134 ms 82,880 KB
testcase_50	AC	293 ms 82,816 KB
testcase_51	AC	462 ms 82,768 KB
testcase_52	AC	299 ms 54,788 KB

権限があれば一括ダウンロードができます

ソースコード

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

結果

テストケース

ソースコード