BOJ - 16991 - 외판원 순회 3

import sys
from math import *

INF = 1e9

def TPS(graph, dp, idx, path, N):

    total = (1 << N) - 1

    if path == total:
        return graph[idx][0] if graph[idx][0] > 0 else INF
    if dp[idx][path] > 0:
        return dp[idx][path]

    tmp = 1e9
    for i in range(1, N):
        if (path >> i) % 2 == 1 or graph[idx][i] == 0:
            continue
        tmp = min(tmp, graph[idx][i] + TPS(graph, dp, i, path|(1 << i), N))
    dp[idx][path] = tmp

    return tmp

def solution():
    N = int(input())
    point = []
    graph = [[0] * N for _ in range(N)]
    dp = [[0] * (1 << N) for _ in range(N)]
    for _ in range(N):
        point.append(list(map(int, sys.stdin.readline().split(' '))))
    
    for i in range(N):
        for j in range(N):
            graph[i][j] = sqrt(
                pow((point[i][0] - point[j][0]), 2) +
                pow((point[i][1] - point[j][1]), 2)
            )

    print("{:.7}".format(TPS(graph, dp, 0, 1, N)))
solution()

https://www.acmicpc.net/problem/16991