C - 巡回セールスマン問題

C - 巡回セールスマン問題

import sys
import math
import heapq
import itertools
from collections import deque
from functools import reduce

def has_bit(n, i):
    return (n & (1<<i) > 0)

# main
def main():
    N = int(input())
    A = []
    for i in range(0, N):
        a = list(map(int, input().split()))
        A.append(a)
    
    ALL = 1<<N
    cost = []
    for n in range(ALL):
        cost.append([10**100]*N)

    cost[0][0] = 0

    for n in range(0, ALL):
        for i in range(0, N):
            for j in range(0, N):
                if has_bit(n, j) or i == j:
                    continue
                cost[n|(1<<j)][j] = min(cost[n|(1<<j)][j], cost[n][i] + A[i][j])

    print(cost[ALL-1][0])

# エントリポイント
if __name__ == '__main__':
    main()