ABC 180 E - Traveling Salesman among Aerial Cities

いわゆる巡回セールスマン問題．$n$ 個の点の間に移動コストが定められていて，点 $0$ から出発し，すべての点を通って点 $0$ に戻ってくるときの最小コストを求める．($n \leq 17$)

E - Traveling Salesman among Aerial Cities

解説

$i$ から $j$ への移動コストが $C[i][j]$ で与えられているものとする．
$V = \{ 0, \ldots , n - 1 \}$ とし，$S \subset V$ と $i \in V$ に対し，$DP[S][i]$ を，$0$ から出発し $S$ 内の点をすべて通って $i$ に到着する経路の最小コストとする．
$0$ は出発点なので，$DP[\phi][0] = 0$ である．$S$ 内の点を全て通って $i$ に到着する経路を $i$ の直前にどの点にいるかによって分類することで， $$ DP[S][i] = \min _ {j \in V} \{ DP[S \setminus \{i\}][j] + C[j][i] \} $$ が成り立つ．

実装

Submission #17514529 - AtCoder Beginner Contest 180

n = int(input())
P = [tuple(map(int, input().split())) for _ in range(n)]
C = [[0] * n for _ in range(n)]
for i in range(n):
    xi, yi, zi = P[i]
    for j in range(n):
        xj, yj, zj = P[j]
        C[i][j] = abs(xi - xj) + abs(yi - yj) + max(0, zj - zi)
DP = [[1 << 30] * n for _ in range(1 << n)]
DP[0][0] = 0
for s in range(1 << n):
    for i in range(n):
        if (1 << i) & s:
            for j in range(n):
                DP[s][i] = min(DP[s][i], DP[s - (1 << i)][j] + C[j][i])
print(DP[(1 << n) - 1][0])