def TSP(ind,visited_city): if dp[ind][visited_city] != INF: return dp[ind][visited_city] if visited_city == (1<<N)-1: if arr[ind][0]: return arr[ind][0] else: return INF for next_city in range(N): if not (visited_city&1<<next_city) and arr[ind][next_city]: temp = TSP(next_city,visited_city|1<<next_city) + arr[ind][next_city] dp[ind][visited_city] = min(dp[ind][visited_city],temp) return dp[ind][visited_city] N = int(input()) arr = [list(map(int,input().split())) for _ in range(N)] INF = float('inf') dp = [[INF]*(2**N) for _ in range(N)] print(TSP(0,1))
'알고리즘 > 백준_복기_미완료' 카테고리의 다른 글
| [BOJ/백준] 2156 포도주 시식 (0) | 2021.05.02 |
|---|---|
| [BOJ/백준] 2141 우체국 (0) | 2021.05.02 |
| [BOJ/백준] 2031 이 쿠키 달지 않아! (0) | 2021.05.02 |
| [BOJ/백준] 1949 우수 마을 (0) | 2021.05.02 |
| [BOJ/백준] 1722 순열의 순서 (0) | 2021.05.02 |