Problem:
Traveling Salesman Problem For a given weighted directed graph G(V, E) , find the distance of the shortest route that meets the following criteria:  It is a closed cycle where it ends at the same point it starts.  It visits each vertex exactly once.  Input  |V|  |E|  s 0  t 0  d 0  s 1  t 1  d 1 : s |E|-1  t |E|-1  d |E|-1   |V| is the number of vertices and |E| is the number of edges in the graph. The graph vertices are named with the numbers 0, 1,..., |V| -1 respectively.  s i and t i represent source and target vertices of i -th edge (directed) and d i represents the distance between s i and t i (the i -th edge). Output Print the shortest distance in a line. If there is no solution, print -1. Constraints  2 ≤ |V| ≤ 15  0 ≤ d i ≤ 1,000  There are no multiedge  Sample Input 1 4 6
0 1 2
1 2 3
1 3 9
2 0 1
2 3 6
3 2 4 Sample Output 1 16 Sample Input 2 3 3
0 1 1
1 2 1
0 2 1 Sample Output 2 -1

Solution (Python):
def main():
    n,m=map(int,input().split())
    inf=10**6
    edges=[[inf]*n for i in range(n)]

    for i in range(m):
        a,b,c=map(int,input().split())
        a-=1
        b-=1
        edges[a][b]=c
    
    
    dp=[[inf]*n for i in range(1<<n)]
    dp[0][0]=0

    for s in range(1<<n):
        for v in range(n):
            for j in range(n):
                if (s>>j)&1 and v!=j and edges[j][v]<10**5:
                    dp[s][v]=min(dp[s][v],dp[s^(1<<j)][j]+edges[j][v])
                    
    if dp[-1][0]>10**5:
        print(-1)
    else:
        print(dp[-1][0])
    
if __name__=='__main__':
    main()

Solution (Python):

import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

v,e=map(int,input().split())
G=[[] for i in range(v)]
for i in range(e):
    s,t,d=map(int,input().split())
    G[s].append((t,d))
dp=[[inf]*v for i in range(2**v)]
dp[1][0]=0
for bit in range(1,2**v):
    for i in range(v):
        if dp[bit][i]==inf: continue
        for gi,di in G[i]:
            if not (bit >> gi & 1):
                dp[bit|1<<gi][gi]=min(dp[bit|1<<gi][gi],dp[bit][i]+di)
            if bit == (1 << v) - 1 and gi == 0:
                dp[bit][0] = min (dp[bit][0],dp[bit][i]+di)
print(dp[2**v-1][0] if dp[2**v-1][0]!=inf else -1)

Solution (Python):
def traveling_salesman(n,edge,INF=10**18):
    dist = [[INF for j in range(n)] for i in range(n)]
    for s,t,d in edge:
        dist[s][t] = d
    dp = [[INF for j in range(n)] for i in range(2**n)]
    dp[2**n-1][0] = 0
    for i in range(2**n-1)[::-1]:
        for j in range(n):
            for k in range(n):
                if not (i>>k & 1):
                    dp[i][j] = min(dp[i][j],dp[i|1<<k][k]+dist[j][k])
    return dp[0][0] if dp[0][0]!=INF else -1

V,E = map(int,input().split())
edge = [tuple(map(int,input().split())) for _ in range(E)]

print(traveling_salesman(V,edge))

Solution (Python):


iim = lambda: map(int, input().rstrip().split())

from heapq import heappush, heappop

def resolve():
    V, E = iim()
    inf = float("inf")
    ad = [[inf]*V for i in range(V)]

    for i in range(E):
        s, t, d = iim()
        ad[s][t] = d

    bi = [1<<i for i in range(V)]
    goal = (1<<V) - 1

    dp = dict()
    q = []
    heappush(q, (0, 0, 1))
    ans = inf
    while q:
        cost, v, state = heappop(q)

        vs = (v, state)
        if vs in dp:
            if dp[vs] <= cost:
                continue
        dp[vs] = cost

        if state == goal:
            cost += ad[v][0]
            if cost < ans:
                ans = cost
            continue

        for i in range(V):
            if bi[i] & state:
                continue
            heappush(q, (cost + ad[v][i], i, state | bi[i]))
    print(ans if ans != inf else -1)
    

if __name__ == "__main__":
    resolve()

Solution (Python):
import heapq
from collections import deque
from enum import Enum
import sys
import math
from _heapq import heappush, heappop
import copy

BIG_NUM = 2000000000
MOD = 1000000007
EPS = 0.000000001


class Edge:
    def __init__(self,arg_to,arg_dist):
        self.to = arg_to
        self.dist = arg_dist


V,E = map(int,input().split())

POW = [None]*(V+1)
POW[0] = 1
for i in range(1,V+1):
    POW[i] = POW[i-1]*2

G = [[] for _ in range(V)]

for _ in range(E):
    from_,to_,dist = map(int,input().split())
    G[from_].append(Edge(to_,dist))


start = 0
dp = [[BIG_NUM]*V for _ in range(POW[V])]

dp[POW[start]][start] = 0

for state in range(1,POW[V]):
    for last_node in range(V):
        if dp[state][last_node] == BIG_NUM:
            continue
        for edge in G[last_node]:
            if state & POW[edge.to] != 0:
                continue 
            next_state = state+POW[edge.to]
            if dp[next_state][edge.to] > dp[state][last_node]+edge.dist:
                dp[next_state][edge.to] = dp[state][last_node]+edge.dist

ans = BIG_NUM

for last_node in range(V):
    if dp[POW[V]-1][last_node] == BIG_NUM:
        continue
    for edge in G[last_node]:
        if edge.to != start:
            continue
        ans = min(ans,dp[POW[V]-1][last_node]+edge.dist)

if ans == BIG_NUM:
    print("-1")
else:
    print("%d"%(ans))

Solution (Python):

INF = 100000000


def make_adj_list(vertex, edge):
    adj_list = []
    dp = []

    
    for i in range(vertex):
        adj_list.append([])
        for j in range(vertex):
            if i == j:
                adj_list[i].append(0)
            else:
                adj_list[i].append(INF)
    for i in range(edge):
        s, t, cost = map(int, input().split())
        adj_list[s][t] = cost

    
    for i in range(1 << vertex):
        dp.append([])
        for j in range(vertex):
            dp[i].append(-1)

    return adj_list, dp


def cal_min_cost(dp, vertex, edge, d, already, now_v):
    if dp[already][now_v] >= 0:
        
        return dp[already][now_v]

    if already == (1 << vertex) - 1 and now_v == 0:
        
        dp[already][now_v] = 0
        return dp[already][now_v]

    res = INF
    for i in range(vertex):
        if not already >> i & 1:
            
            res = min(res, cal_min_cost(dp, vertex, edge, d,
                      already | 1 << i, i) + d[now_v][i])
    dp[already][now_v] = res
    return dp[already][now_v]


def main():
    vertex, edge = map(int, input().split())
    adj_list, dp = make_adj_list(vertex, edge)  
    
    d = adj_list
    
    
    
    
    
    
    min_cost = cal_min_cost(dp, vertex, edge, d, 0, 0)  
    if min_cost == INF:
        print(-1)
    else:
        print(int(min_cost))


if __name__ == "__main__":
    main()

Solution (Python):
import itertools
V, E = [int(_) for _ in input().split()]
STD = [[int(_) for _ in input().split()] for _ in range(E)]
G = [[float('inf')] * V for _ in range(V)]
for s, t, d in STD:
    G[s][t] = d
ans = float('inf')
dp = [[float('inf')] * V for _ in range(2**V)]

for start in range(1):
    dp[(2**V - 1)][start] = 0
    for S in range(2**V - 1 - 2**start, -1, -1):
        for v in range(V):
            for u in range(V):
                if not (S >> u & 1):
                    dp[S][v] = min(dp[S][v], dp[S | 1 << u][u] + G[v][u])
    ans = min(ans, dp[0][start])
if ans == float('inf'):
    print(-1)
else:
    print(ans)

Solution (Python):
def tsp(matrix):
    INF = float("inf")
    n = len(matrix)

    
    
    dp = [[INF]*n for i in range(1 << n)]
    dp[1 << 0][0] = 0
 
    for bit_state in range(1 << n):
        for i in range(n):
            
            if (bit_state >> i) & 1:
                for j in range(n):
                    
                    if not ((bit_state >> j) & 1):
                        dp[bit_state|(1 << j)][j] = min(dp[bit_state|(1 << j)][j], dp[bit_state][i] + matrix[i][j])
    ans = INF
    for i in range(n):
        ans = min(dp[(1 << n) - 1][i] + matrix[i][0], ans)
    return ans

n, m = map(int, input().split())
info = [list(map(int, input().split())) for i in range(m)]
INF = float("inf")

matrix = [[INF]*n for i in range(n)]
for i in range(m):
    a, b, cost = info[i]
    matrix[a][b] = cost
for i in range(n):
    matrix[i][i] = 0

ans = tsp(matrix)
if ans == INF:
    print(-1)
else:
    print(ans)

Solution (Python):
import sys
from typing import List, Tuple


def rec(state: int, v: int, dp: List[List[int]],
        edges: List[List[Tuple[int, int]]]) -> int:
    if (dp[state][v] >= 0):
        return dp[state][v]
    if ((1 << V) - 1 == state and v == 0):
        
        dp[state][0] = 0
        return 0

    ans = sys.maxsize
    for to, cost in edges[v]:
        if (not (state >> to & 1)):
            ans = min(ans, rec(state | 1 << to, to, dp, edges) + cost)
    dp[state][v] = ans
    return ans


if __name__ == "__main__":
    V, E = map(lambda x: int(x), input().split())
    edges: List[List[Tuple[int, int]]] = [[] for _ in range(V)]
    for _ in range(E):
        source, target, cost = map(lambda x: int(x), input().split())
        edges[source].append((target, cost))

    dp = [[-1] * V for _ in range(1 << V)]
    print(dp[0][0] if rec(0, 0, dp, edges) != sys.maxsize else -1)

Solution (Python):


import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N, M = MAP()
G = list2d(N, N, INF)
for i in range(M):
    s, t, d = MAP()
    G[s][t] = d


dp = list2d(1<<N, N, INF)

dp[1][0] = 0

for bit in range(1, (1<<N)-1):
    for i in range(N):
        
        if not bit>>i&1: continue
        for j in range(N):
            
            if bit>>j&1: continue
            
            dp[bit+(1<<j)][j] = min(dp[bit+(1<<j)][j], dp[bit][i] + G[i][j])

mn=INF
for end in range(N):
    
    mn = min(mn, dp[(1<<N)-1][end] + G[end][0])
if mn==INF:
    print(-1)
else:
    print(mn)

Solution (Python):
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(input())
def inpl(): return list(map(int, input().split()))
def inpl_str(): return list(input().split())

N,M = inpl()
lines = defaultdict(set)
for _ in range(M):
    s,t,d = inpl()
    lines[s].add((t,d))


S = 0
dp = [[INF]*N for _ in range(1<<(N+1)-1)]
dp[0][S] = 0
for bit in range(1<<(N+1)-1):
    for s in range(N):
        now = dp[bit][s]
        for t,c in lines[s]:
            if bit & (1<<t): 
                continue
            else:
                dp[bit+(1<<t)][t] = min(dp[bit+(1<<t)][t],now+c)

ans = dp[-1][S]
if ans == INF:
    print(-1)
else:
    print(dp[-1][S])

Solution (Python):

"""
Permutation/Path - Traveling Salesman Problem
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_2_A&lang=jp

"""


V, E = map(int, input().split())

d = [[float('inf')]*V for _ in range(V)]
for _ in range(E):
    f, t, dist = map(int, input().split())
    d[f][t] = dist
dp = [[-1]*V for _ in range(2**V)]


def solve(S, v):
    if dp[S][v] >= 0:
        return dp[S][v]
    if (S == 2**V-1) and (v == 0):
        dp[S][v] = 0
        return 0
    res = float('inf')
    for u in range(V):
        if not ((S >> u) & 1):
            res = min(res, solve(S | (1 << u), u) + d[v][u])
    dp[S][v] = res
    return res

ans = solve(0, 0)
if ans == float('inf'):
    print(-1)
else:
    print(ans)

Solution (Python):
N, M = map(int, input().split())
G = [[float('inf')] * N for i in range(N)]
for i in range(M):
    s, t, d = map(int, input().split())
    s, t = s - 1, t- 1
    G[s][t] = d

dp = [[float('inf')] * N for i in range(2 ** N)]
dp[1][0] = 0

for bs in range(2 ** N):
    for i in range(N):
        if not bs & (1 << i):
            continue
        for j in range(N):
            if bs & (1 << j):
                continue
            dp[bs | (1 << j)][j] = min(dp[bs | (1 << j)][j], dp[bs][i] + G[i][j])

ans = float('inf')
for i in range(N):
    ans = min(ans, dp[-1][i] + G[i][0])

print(ans if ans != float('inf') else - 1)

Solution (Python):
dp = []
dist = []
INF = 1000000000

def tsp(s, v, dp, n):
    if dp[s][v] >= 0:
        return dp[s][v]
    if s == (1<<n)-1 and v == 0:
        dp[s][v] = 0
        return 0
    res = INF
    for u in range(n):
        if (s >> u & 1) == 0:
            res = min(res, tsp(s | (1 << u), u, dp, n) + dist[v][u])
    dp[s][v] = res
    return res
    
line = input()
v, e = list(map(int, line.split()))
dp = [ [-1] * v for _ in range(0, 1 << v)]
dist = [ [INF] * v for _ in range(0, v)]
for _ in range(0, e):
    line = input()
    s, t, d = list(map(int, line.split()))
    dist[s][t] = d
ans = tsp(0, 0, dp, v)
print(ans if ans < INF else -1)

Solution (Python):
INF = float('inf')
n, k = map(int, input().split())
G = [[] for _ in range(n)]
_G = []
for _ in range(k):
    ss, t, d = map(int, input().split())
    G[ss].append((t,d))
    if t == 0:_G.append((ss,d))
    
dp = [[INF]*n for _ in range(1<<n)]
dp[1][0] = 0

for s in range(1,(1<<n)):
    for v in range(n):
        if dp[s][v] == INF:continue
        for t, d in G[v]:
            if not(s & (1<<t)):
                next_s = s | (1<<t)
                dp[next_s][t] = min(dp[next_s][t],dp[s][v]+d)
                    
                    
ans = INF
for pre, d in _G:
    ans = min(ans, dp[-1][pre]+d)
print(ans if ans != INF else -1)

Solution (Python):
INF = 10 ** 10
v, e = map(int, input().split())
adj = [[INF] * v for _ in range(v)]
for _ in range(e):
    s, t, d = map(int, input().split())
    adj[s][t] = d

mem = {}
end = 2 ** v - 1
def minCost(state, pos):
    if (state, pos) in mem:
        return mem[(state, pos)]

    if state == end:
        return adj[pos][0]

    mask = 1
    ret = INF
    for to in range(v):
        if mask & state:
            mask <<= 1
            continue

        ret = min(ret, adj[pos][to] + minCost(state | mask, to))
        mask <<= 1

    mem[(state, pos)] = ret
    return ret

result = minCost(1, 0)
if result >= INF:
    print(-1)
else:
    print(result)

Solution (Python):
def rec(visited,curpos):
    if (dp[visited][curpos] >= 0): return dp[visited][curpos]

    if (curpos == 0) & (visited == ((1 << v) - 1)) : 
        dp[visited][curpos] = 0
        return 0
    ret = float('inf')
    for i in range(v):
        if not ((visited >> i) & 1):
            ret = min(ret , rec((visited | 1 << i) , i ) + dis[curpos][i])
    dp[visited][curpos] = ret
    return ret

v,e = map(int, input().split())
dis = [[float('inf') for i in range(v)] for j in range(v)]
dp = [[-1 for j in range(v)] for k in range(1 << v)]

for i in range(e):
    s,t,d = map(int, input().split())
    dis[s][t] = d

ans = float('inf')
rec(0,0)
ans = min(ans , dp[0][0])

if ans == float('inf'):
    print('-1')
else:
    print(ans)

Solution (Python):
V, E = map(int, input().split())


distance_list = [[float('inf') for i in range(V)] for j in range(V)]
for i in range(V):
    distance_list[i][i] = 0
for node in range(E):
    start, goal, distance = map(int, input().split())
    distance_list[start][goal] = distance

dp = [[-1 for v in range(V)] for S in range(1 << V)]
def TSP(S, v):
    if dp[S][v] >= 0:
        return dp[S][v]
    else:
        if S == (1 << V) - 1 and v == 0:
            dp[S][v] = 0
            return 0
        else:
            ans = float('inf')
            for u in range(V):
                if (S >> u) & 1 == 0:
                    ans = min(ans, TSP(S | (1 << u), u) + distance_list[v][u])
            dp[S][v] = ans
            return ans
if TSP(0,0) == float('inf'):
    print(-1)
else:
    print(TSP(0,0))