#673244 (C) No.1599 Hikyaku

提出ソース

結果

問題	No.1599 Hikyaku
ユーザー	👑 ygussany
提出日時	2021-07-06 11:08:16
言語	C (gcc 12.3.0)
結果	AC
実行時間	1,536 ms / 7,500 ms
コード長	6,268 bytes
コンパイル時間	514 ms
コンパイル使用メモリ	37,900 KB
実行使用メモリ	120,612 KB
最終ジャッジ日時	2023-09-14 07:01:56
合計ジャッジ時間	35,854 ms
ジャッジサーバーID （参考情報）	judge14 / judge12

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	102 ms 114,612 KB
testcase_01	AC	126 ms 115,768 KB
testcase_02	AC	132 ms 118,532 KB
testcase_03	AC	92 ms 75,876 KB
testcase_04	AC	1,091 ms 117,560 KB
testcase_05	AC	420 ms 76,788 KB
testcase_06	AC	1,470 ms 107,148 KB
testcase_07	AC	378 ms 68,736 KB
testcase_08	AC	1,536 ms 109,716 KB
testcase_09	AC	99 ms 59,208 KB
testcase_10	AC	309 ms 65,668 KB
testcase_11	AC	101 ms 59,124 KB
testcase_12	AC	275 ms 75,732 KB
testcase_13	AC	259 ms 96,732 KB
testcase_14	AC	95 ms 61,224 KB
testcase_15	AC	104 ms 120,612 KB
testcase_16	AC	403 ms 114,980 KB
testcase_17	AC	1,096 ms 115,880 KB
testcase_18	AC	1,099 ms 117,760 KB
testcase_19	AC	1,402 ms 119,700 KB
testcase_20	AC	1,467 ms 120,076 KB
testcase_21	AC	1,388 ms 118,732 KB
testcase_22	AC	1,391 ms 118,692 KB
testcase_23	AC	1,279 ms 116,664 KB
testcase_24	AC	1,319 ms 117,080 KB
testcase_25	AC	1,201 ms 118,640 KB
testcase_26	AC	1,000 ms 118,640 KB
testcase_27	AC	594 ms 114,640 KB
testcase_28	AC	597 ms 116,536 KB
testcase_29	AC	420 ms 114,632 KB
testcase_30	AC	261 ms 117,004 KB
testcase_31	AC	102 ms 114,572 KB
testcase_32	AC	102 ms 116,584 KB
testcase_33	AC	102 ms 114,524 KB
testcase_34	AC	596 ms 118,592 KB
testcase_35	AC	790 ms 117,324 KB
testcase_36	AC	1,157 ms 118,564 KB
testcase_37	AC	1,128 ms 114,652 KB
testcase_38	AC	1,089 ms 117,140 KB
testcase_39	AC	1,085 ms 117,704 KB
testcase_40	AC	1,112 ms 118,340 KB
testcase_41	AC	88 ms 61,220 KB
testcase_42	AC	103 ms 114,696 KB
testcase_43	AC	90 ms 61,276 KB
testcase_44	AC	409 ms 116,476 KB
testcase_45	AC	404 ms 117,252 KB
testcase_46	AC	561 ms 114,708 KB
testcase_47	AC	567 ms 116,988 KB
testcase_48	AC	1,078 ms 118,576 KB
testcase_49	AC	102 ms 118,568 KB
testcase_50	AC	248 ms 116,524 KB
testcase_51	AC	399 ms 114,628 KB
testcase_52	AC	257 ms 65,328 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

結果

テストケース

ソースコード