Edit

【pythonでABC180を解説】E - Traveling Salesman among Aerial Cities

問題概要

問題ページ

E - Traveling Salesman among Aerial Cities
E - Traveling Salesman among Aerial Cities

問題ページへ移動する

問題文

\(3\) 次元空間内に \(N\) 個の都市、都市 \(1\) から 都市 \(N\) があります。都市 \(i\) は座標 \((X_i,Y_i,Z_i)\) にあります。

座標 \((a,b,c)\) の都市から \((p,q,r)\) の都市に移動する際には \(|p-a|+|q-b|+\max(0,r-c)\) のコストがかかります。

都市 \(1\) からスタートし、全ての都市を \(1\) 度以上巡って都市 \(1\) に戻るまでの最小コストを求めてください。

制約

  • \(2 \leq N \leq 17\)
  • \(-10^6 \leq X_i,Y_i,Z_i \leq 10^6\)
  • 同じ座標に複数の都市があることはない
  • 入力は全て整数

問題の考察

ACコード

import sys


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    n = int(input().rstrip('\n'))
    xyz = [list(map(int, input().rstrip('\n').split())) for _ in range(n)]
    dp = [[10 ** 10] * (sum([2 ** i for i in range(n)]) + 1) for _ in range(n)]
    dp[0][1] = 0
    for k in range(sum([2 ** i for i in range(n)]) + 1):
        for i in range(n):
            if dp[i][k] != 10 ** 10:
                for j in range(n):
                    dp[j][k | 2 ** j] = min(dp[j][k | 2 ** j], dp[i][k] + abs(xyz[j][0] - xyz[i][0]) + abs(xyz[j][1] - xyz[i][1]) + max(0, xyz[j][2] - xyz[i][2]))
    print(dp[0][-1])


if __name__ == '__main__':
    solve()

-Edit
-