結果
| 問題 |
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 |
ソースコード
#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;
}