Submission #17459018

---

Source Code Expand

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

Judge Result