travelling sales man problem dp

Given a matrix cost of size n where cost[i][j] denotes the cost of moving from city i to city j. Your task is to complete a tour from the city 0 (0 based index) to all other cities such that you visit each city atmost once and then at the end come back to city 0 in min cost.








#User function Template for python3
from functools import lru_cache
import sys
class Solution:
    def total_cost(self, cost):
        #Code here
        n=len(cost)
        v_all=(1<<n)-1
        dp=[[-1 for i in range(n)] for j in range(1<<n)]
        def compute(mask,pos):
            if dp[mask][pos]!=-1:
                return dp[mask][pos]
            if mask==v_all:
                return cost[pos][0]
            else:
                ans=sys.maxsize
                for city in range(n):
                    if (1<<city)&mask==0:
                        temp=cost[pos][city]+compute((1<<city)|mask,city)
                        ans=min([temp,ans])
            dp[mask][pos]=ans
            return ans
        return compute(1,0)




#{
#  Driver Code Starts
#Initial Template for Python 3

if __name__ == '__main__':
    T=int(input())
    for i in range(T):
        n = int(input())
        cost = []
        for _ in range(n):
            cost.append(list(map(int, input().split())))
        obj = Solution()
        ans = obj.total_cost(cost)
        print(ans)

# } Driver Code Ends