# BOJ - 10971 - 외판원 순회 2

Updated:

```
import sys
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())
graph = []
dp = [[0] * (1 << N) for _ in range(N)]
for _ in range(N):
graph.append(list(map(int, sys.stdin.readline().split())))
print(TPS(graph, dp, 0, 1, N))
solution()
```

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

## Leave a comment