[백준 16991번] 외판원 순회 3 (Python3)

import sys,math
input = sys.stdin.readline
INF = 10**9

N = int(input())
co = [[*map(int,input().split())] for i in range(N)]
graph = [[0]*N for i in range(N)]
for i in range(N-1):
  x1,y1 = co[i]
  for j in range(i,N):
    x2,y2 = co[j]
    graph[i][j]=graph[j][i]=math.sqrt((x1-x2)**2+(y1-y2)**2)

DP = [[-1]*N for i in range(1<<N)]

def DFS(bit,now):
  if bit+1 == 1<<N:
    if graph[now][0]:
      DP[bit][now] = graph[now][0]
    else:
      DP[bit][now] = INF
    return
  if DP[bit][now] != -1:
    return
  for next in range(N):
    if bit & 1<<next:
      continue
    if not graph[now][next]:
      if DP[bit][now] == -1:
        DP[bit][now] = INF
      continue
    DFS(bit|1<<next,next)
    if DP[bit|1<<next][next] == INF:
      if DP[bit][now] == -1:
        DP[bit][now] = INF
      continue
    if DP[bit][now] > graph[now][next]+DP[bit|1<<next][next] or DP[bit][now] == -1:
      DP[bit][now] = graph[now][next]+DP[bit|1<<next][next]

DFS(1,0)
print(DP[1][0])

외판원 순회 [백준 2098번] 외판원 순회 (Python3) (tistory.com) 와 똑같은 문제로, 그래프를 입력받는 방식만 달라졌다.

외판원 순회 문제 코드를 그냥 복붙하고 그래프만 바꿔주면 된다.