Contest Duration: ~ (local time) (100 minutes) Back to Home

Submission #17459018

Source Code Expand

Copy
```import sys
import numpy as np
import numba
from numba import njit, b1, i4, i8, f8

@njit((i8[:], ), cache=True)
def main(XYZ):
X, Y, Z = XYZ[::3], XYZ[1::3], XYZ[2::3]
N = len(X)

D = np.zeros((N, N), np.int64)
for i in range(N):
for j in range(N):
D[i, j] = abs(X[i] - X[j]) + abs(Y[i] - Y[j]) + max(0, Z[j] - Z[i])

# 出発は 1 限定
INF = 1 << 60
dp = np.full((1 << N, N), INF, np.int64)
# subset, last
dp[1, 0] = 0
for s in range(1, 1 << N):
for frm in range(N):
if dp[s, frm] == INF:
continue
for to in range(N):
t = s | 1 << to
if s == t:
continue
dp[t, to] = min(dp[t, to], dp[s, frm] + D[frm, to])
return np.min(dp[-1] + D[:, 0])

XYZ = np.array(read().split(), np.int64)

print(main(XYZ))

```

#### Submission Info

Submission Time 2020-10-17 20:31:53+0900 E - Traveling Salesman among Aerial Cities maspy Python (3.8.2) 500 1048 Byte AC 543 ms 124072 KB

#### Judge Result

Set Name Sample All
Score / Max Score 0 / 0 500 / 500
Status
 AC × 3
 AC × 23
Set Name Test Cases
Sample sample_01.txt, sample_02.txt, sample_03.txt
All random_01.txt, random_02.txt, random_03.txt, random_04.txt, random_05.txt, random_06.txt, random_07.txt, random_08.txt, random_09.txt, random_10.txt, random_11.txt, random_12.txt, random_13.txt, random_14.txt, random_15.txt, random_16.txt, random_17.txt, random_18.txt, random_19.txt, random_20.txt, sample_01.txt, sample_02.txt, sample_03.txt
Case Name Status Exec Time Memory
random_01.txt 543 ms 123512 KB
random_02.txt 481 ms 106688 KB
random_03.txt 507 ms 123224 KB
random_04.txt 509 ms 123520 KB
random_05.txt 515 ms 123360 KB
random_06.txt 473 ms 106200 KB
random_07.txt 528 ms 122544 KB
random_08.txt 475 ms 107424 KB
random_09.txt 521 ms 124072 KB
random_10.txt 475 ms 106012 KB
random_11.txt 518 ms 123420 KB
random_12.txt 482 ms 105444 KB
random_13.txt 522 ms 123580 KB
random_14.txt 479 ms 105964 KB
random_15.txt 515 ms 123312 KB
random_16.txt 471 ms 107456 KB
random_17.txt 527 ms 123468 KB
random_18.txt 476 ms 106556 KB
random_19.txt 512 ms 124012 KB
random_20.txt 468 ms 107052 KB
sample_01.txt 471 ms 106120 KB
sample_02.txt 489 ms 105424 KB
sample_03.txt 511 ms 123052 KB