Submission #17459018


Source Code Expand

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

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

@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])

N = int(readline())
XYZ = np.array(read().split(), np.int64)

print(main(XYZ))

Submission Info

Submission Time
Task E - Traveling Salesman among Aerial Cities
User maspy
Language Python (3.8.2)
Score 500
Code Size 1048 Byte
Status
Exec Time 543 ms
Memory 124072 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 500 / 500
Status
× 3
× 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