#673244 (C) No.1599 Hikyaku

提出ソース

結果

問題	No.1599 Hikyaku
ユーザー	👑 ygussany
提出日時	2021-07-06 11:08:16
言語	C (gcc 11.2.0)
結果	AC
実行時間	1,530 ms / 7,500 ms
コード長	6,268 bytes
コンパイル時間	302 ms
使用メモリ	87,108 KB
最終ジャッジ日時	2023-02-01 21:10:29
合計ジャッジ時間	37,187 ms
ジャッジサーバーID （参考情報）	judge12 / judge13

このコードへのチャレンジ（β）

テストケース

テストケース表示

入力	結果	実行時間使用メモリ
testcase_00	AC	129 ms 82,916 KB
testcase_01	AC	150 ms 84,068 KB
testcase_02	AC	159 ms 84,000 KB
testcase_03	AC	112 ms 60,292 KB
testcase_04	AC	1,139 ms 84,204 KB
testcase_05	AC	447 ms 61,688 KB
testcase_06	AC	1,475 ms 79,864 KB
testcase_07	AC	385 ms 57,444 KB
testcase_08	AC	1,530 ms 79,928 KB
testcase_09	AC	115 ms 49,288 KB
testcase_10	AC	323 ms 54,936 KB
testcase_11	AC	117 ms 49,040 KB
testcase_12	AC	293 ms 60,492 KB
testcase_13	AC	283 ms 71,536 KB
testcase_14	AC	109 ms 49,120 KB
testcase_15	AC	130 ms 82,852 KB
testcase_16	AC	430 ms 82,828 KB
testcase_17	AC	1,134 ms 84,348 KB
testcase_18	AC	1,154 ms 84,668 KB
testcase_19	AC	1,449 ms 87,108 KB
testcase_20	AC	1,433 ms 87,028 KB
testcase_21	AC	1,381 ms 85,816 KB
testcase_22	AC	1,374 ms 85,032 KB
testcase_23	AC	1,314 ms 84,456 KB
testcase_24	AC	1,318 ms 84,356 KB
testcase_25	AC	1,259 ms 84,328 KB
testcase_26	AC	1,044 ms 83,740 KB
testcase_27	AC	633 ms 83,140 KB
testcase_28	AC	635 ms 83,296 KB
testcase_29	AC	441 ms 82,932 KB
testcase_30	AC	283 ms 82,984 KB
testcase_31	AC	130 ms 82,824 KB
testcase_32	AC	129 ms 82,772 KB
testcase_33	AC	128 ms 82,848 KB
testcase_34	AC	621 ms 82,896 KB
testcase_35	AC	809 ms 83,336 KB
testcase_36	AC	1,193 ms 83,464 KB
testcase_37	AC	1,152 ms 83,700 KB
testcase_38	AC	1,118 ms 83,548 KB
testcase_39	AC	1,124 ms 84,020 KB
testcase_40	AC	1,133 ms 85,064 KB
testcase_41	AC	103 ms 49,136 KB
testcase_42	AC	128 ms 82,836 KB
testcase_43	AC	106 ms 49,196 KB
testcase_44	AC	431 ms 82,836 KB
testcase_45	AC	433 ms 82,832 KB
testcase_46	AC	591 ms 82,828 KB
testcase_47	AC	591 ms 82,988 KB
testcase_48	AC	1,103 ms 83,004 KB
testcase_49	AC	125 ms 82,880 KB
testcase_50	AC	272 ms 82,832 KB
testcase_51	AC	429 ms 82,832 KB
testcase_52	AC	278 ms 54,692 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

結果

テストケース

ソースコード