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):

V, E = map(int, input().split())
dist = [[float("inf")] * (V + 1) for i in range(V + 1)]
for i in range(E):
  s, t, d = map(int, input().split())
  dist[s][t] = d
  
for i in range(V):  
  dist[i][i] = 0
  


dp = [[-1] * (V + 1) for i in range(2 ** V + 1)]

def rec(bit, v):
  
  if dp[bit][v] != -1:
    return dp[bit][v]
  
  
  if bit == (1 << 0):
    dp[bit][0] = 0
    return 0
  
  res = float("inf")
  prev_bit = bit & ~(1 << v)
  
  for i in range(V):
    if not (prev_bit & (1 << i)):
      continue
    else:
      res = min(res, rec(prev_bit, i) + dist[i][v])
  
  dp[bit][v] = res
  return res

ans = float("inf")
for i in range(V):
  ans = min(ans, rec((1 << V) - 1, i) + dist[i][0])
  

if ans >= 1000000:
  print(-1)
else:
  print(ans)

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):


import sys
sys.setrecursionlimit(10 ** 9)

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

cost = [[float("inf")]*V for _ in range(V)]
for _ in range(E):
    s, t, d = map(int, input().split())
    cost[s][t] = d

dp = [[float("inf")]*(V) for _ in range((1<<V))]

dp[0][0] = 0                                
                                            

for S in range(1<<V):
    for v in range(V):
        if not (1<<v)&S:                    
            dp[S|(1<<v)][v] = min(dp[S][u] + cost[u][v] for u in range(V))
                                            
                                            
                                            
                                            

if dp[(1<<V)-1][0] == float("inf"):
    print(-1)
else:
    print(dp[(1<<V)-1][0])

Solution (Python):
def TS(G,v,e):
    INF = 16000
    DP = [[INF for _ in range(v)] for _ in range(2**v)]
    
    DP[0][0] = 0
    
    for i in range(2**v):
        for j in range(v):
            for k in range(v):
                if i ^ 2**k < i and j != k \
                and DP[i ^ 2**k][k] + G[k][j] < DP[i][j]:
                    DP[i][j] = DP[i ^ 2**k][k] + G[k][j]

    if DP[2**v-1][0] != INF:
        return DP[2**v-1][0]
    else:
        return -1

def main():
    v,e = map(int,input().split())
    INF = 16000
    G = [[INF for _ in range(v)] for _ in range(v)]
    for i in range(e):
        s,t,d = map(int,input().split())
        G[s][t] = d

    print(TS(G,v,e))

if __name__ == "__main__":
    main()

Solution (Python):
def salesman(T, now_v, dp, graph, v):
    if dp[T][now_v] >= 0:
        return dp[T][now_v]
    if T == (1 << v) - 1 and now_v == 0:
        dp[T][now_v] = 0
        return dp[T][now_v]
    res = 10 ** 7
    for i in range(v):
        if not ((T >> i) & 1):
            res = min(res, salesman(T | (1 << i), i, dp, graph, v) + graph[now_v][i])
    dp[T][now_v] = res
    return dp[T][now_v]


def main():
    v, e = map(int, input().split())
    INF = 10 ** 7
    graph = [[INF for i in range(v)] for j in range(v)]
    for i in range(e):
        s, t, d = map(int, input().split())
        graph[s][t] = d
    dp = []
    for i in range(1 << v):
        dp.append([])
        for j in range(v):
            dp[i].append(-1)
    salesman(0, 0, dp, graph, v)
    if dp[0][0] >= INF:
        print(-1)
    else:
        print(dp[0][0])
    
    




if __name__ == '__main__':
    main()

Solution (Python):


from pprint import pprint
from collections import deque, defaultdict
import itertools
import math
import sys

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.buffer.readline
INF = 10 ** 10

n_nodes, m_edges = map(int, input().split())
dist = [[INF] * n_nodes for _ in range(n_nodes)]

for _ in range(m_edges):
    s, t, d = map(int, input().split())
    dist[s][t] = d

memory = {}
end = 2 ** n_nodes - 1


def rec(state, pos):
    if (state, pos) in memory:
        return memory[(state, pos)]

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

    mask = 1
    res = INF
    for pos_next in range(n_nodes):
        if mask & state:
            mask <<= 1
            continue

        res = min(res, rec(state | mask, pos_next) + dist[pos][pos_next])
        mask <<= 1

    memory[(state, pos)] = res
    return res


res = rec(1, 0)
if res == INF:
    print(-1)
else:
    print(res)

Solution (Python):
import sys
input = sys.stdin.readline

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


dist = [[float("inf")] * V for i in range(V)]
for _ in range(E):
    s, t, d = map(int, input().split())
    dist[s][t] = d

dp = [[-1] * V for i in range(2**V)]


def rec(s, v, dp):
    
    if dp[s][v] >= 0:
        return dp[s][v]
    
    
    if s == 2**V - 1 and v == 0:
        dp[s][v] = 0
        return 0
    
    res = 10**100
    for i in range(V):
        if (s>>i & 1) == 0:
            
            
            res = min(res, rec(s|(1<<i), i, dp) + dist[v][i])
    
    dp[s][v] = res
    return dp[s][v]

ans = rec(0, 0, dp)
if ans == 10**100:
    ans = -1
print(ans)

Solution (Python):




'''
定式化(本は"集める"DPで定義してるが、わかりやすさのため"配る"DPで定式化)

ノーテーション
S ... 頂点集合
| ... 和集合演算子
dp[S][v] ... 重みの総和の最小。頂点0から頂点集合Sを経由してvに到達する。

更新則
dp[S|{v}] = min{dp[S][u]+d(u,v) | u∈S} ただしv∉S

初期条件
dp[∅][0] = 0 
dp[V][u] = INF 

答え
dp[すべての要素][0] ... 0からスタートしてすべての要素を使って最後に0に戻るための最小コスト
'''


INF = 2 ** 31
from itertools import product


def solve(n, graph):
    '''nは頂点数、graphは隣接行列形式'''
    max_S = 1 << n  
    dp = [[INF] * n for _ in range(max_S)]
    dp[0][0] = 0
    for S in range(max_S):
        for u, v in product(range(n), repeat=2):
            if (S >> v) & 1 == 1:  
                continue
            dp[S | (1 << v)][v] = min(dp[S | (1 << v)][v],
                                      dp[S][u] + graph[u][v])
    print(dp[-1][0] if dp[-1][0] != INF else -1)













n, e = map(int, input().split())
graph = [[INF] * n for _ in range(n)]
for _ in range(e):
    s, t, d = map(int, input().split())
    graph[s][t] = d
solve(n, graph)

Solution (Python):
inf=float("inf")
v,e=map(int,input().split())
STD=[list(map(int,input().split())) for _ in range(e)]

D=[[inf for _ in range(v)] for _ in range(v)]
for s,t,d in STD:
    D[s][t]=d

DP=[[-1 for _ in range(v)] for _ in range(1<<v)]


def bitDP(s,g,DP):
    if DP[s][g]>=0:return DP[s][g]
    if s==(1<<v)-1 and g==0:
        DP[s][g]=0
        return 0

    ans=inf
    for i in range(v):
        if (s>>i & 1)==0:
            ans=min(ans,bitDP(s|(1<<i),i,DP)+D[g][i])
    DP[s][g]=ans
    return ans


ans=bitDP(0,0,DP)
print(ans if ans!=inf else -1)

Solution (Python):
V,E = map(int,input().split())
dist = [[float("inf")]*V for _ in range(V)]
for i in range(E):
    s,t,d = map(int,input().split())
    dist[s][t] = d
dp = [[-1]*V for i in range(1<<V)] 


def rec(s,v,dp):
    if dp[s][v] >= 0:
        return dp[s][v]  
        
    if s == (1<<V)-1 and v == 0:
        
        dp[s][v] = 0
        return 0
    
    res = float("inf")
    for u in range(V):
        if (s>>u&1) == 0:
            
            res = min(res,rec(s|(1<<u),u,dp)+dist[v][u])
            
    dp[s][v] = res
    return res
a = rec(0,0,dp)
if a == float("inf"):
    print(-1)
else:
    print(a)

Solution (Python):
v, e = map(int, input().split())
G = [[float('inf')]*v for _ in range(v)]
for _ in range(e):
    s, t, d = map(int, input().split())            
    G[s][t] = d
dist = [[float("inf")]*v for _ in range(1<<v)]
dist[1][0] = 0
for s in range(1<<v):
    for i in range(v):
        for j in range(v):
            
            if (s>>i)&1 == 1:continue
            if (s>>j)&1 == 0:continue
            dist[(1<<i|s)][i] = min(dist[1<<i|s][i], dist[s][j] + G[j][i])

ans = float('inf')
for i in range(v):
    ans = min(ans, dist[(1<<v)-1][i] + G[i][0])
print(ans if ans != float('inf') else -1)

Solution (Python):
from sys import stdin
from sys import setrecursionlimit
setrecursionlimit(10**9)

readline=stdin.readline
n,w=map(int,readline().split())
INF=10**9
G=[[INF]*n for _ in range(n)]

for _ in range(w):
    s,t,d=map(int,readline().split())
    G[s][t]=d

dp=[[-1]*n for _ in range(1<<n)]

def func(s,v):
    if dp[s][v]>=0: return dp[s][v]

    if (s==(1<<n)-1) and v==0:
        dp[s][v]=0
        return dp[s][v]

    tmp=INF
    for u in range(n):
        t=(1<<u)|s
        if t==s: continue
        tmp=min(tmp,func(t,u)+G[v][u])
    dp[s][v]=tmp
    return dp[s][v]

ans=func(0,0)
print(ans if ans<INF else -1)

Solution (Python):
INF=10**18
V,E=map(int,input().split())
G=[[INF]*V for i in range(V)]
for i in range(E):
    s,t,d=map(int,input().split())
    G[s][t]=d
ans=INF
dp=[[INF]*V for i in range(1<<V)]
dp[0][0]=0
    
for S in range(1<<V):
    for v in range(V):
        if S&(1<<v):
            for j in range(V):
                dp[S][v]=min(dp[S][v],dp[S-(1<<v)][j]+G[j][v])
print(dp[(1<<V)-1][0] if dp[(1<<V)-1][0]!=INF else -1)

Solution (Python):

import sys
sys.setrecursionlimit(10 ** 7)
read = sys.stdin.buffer.read
inp = sys.stdin.buffer.readline
def inpS(): return inp().rstrip().decode()
readlines = sys.stdin.buffer.readlines
MOD = 10 ** 9 + 7
INF = 1 << 60





def resolve():
    def rec(S, v):
        if dp[S][v] >= 0:
            return dp[S][v]
        if S == (1<<V)-1 and v==0:
            dp[S][v] = 0
            return 0
        res = INF
        for to in range(V):
            if not (S>>to & 1):
                res = min(res, rec((S | (1<<to)), to) + dist[v][to])

        dp[S][v] = res
        return res

    V, E = map(int, input().split())
    dist = [[INF] * V for _ in range(V)]
    for i in range(E):
        x, y, d = map(int, input().split())
        dist[x][y] = d

    dp = [[-1] * V for _ in range(1 << V)]

    res = rec(0, 0)
    if res == INF:
        print(-1)
    else:
        print(res)

if __name__ == '__main__':
    resolve()

Solution (Python):
import sys
input = sys.stdin.readline
INF = 10**12
V, E = map(int, input().split())
d = [[INF]*(V) for _ in range(V)]
for i in range(E):
    s, t, dd = map(int, input().split())
    d[s][t] = dd
def f():
    
    dp = [[INF]*(V) for _ in range(1<<V)]
    dp[(1<<V)-1][0] = 0
    for i in range((1<<V)-2, -1, -1):
        for j in range(V):
            for k in range(V):
                if not (i>>k & 1):
                    dp[i][j] = min(dp[i][j], dp[i | 1 << k][k]+ d[j][k])
    if dp[0][0] < INF:
        print(dp[0][0])
    else:
        print(-1)
    
f()

Solution (Python):
from typing import List

INT_INF = -1

class Graph:
    v_num: int
    edges: List[List[int]]

    def __init__(self, v_num: int):
        self.v_num = v_num
        self.edges = [[INT_INF for c in range(v_num)] for r in range(v_num)]

    def setDist(self, src: int, dest: int, dist: int):
        self.edges[src][dest] = dist


class TSPSolver:
    g: Graph

    def __init__(self, g: Graph):
        self.g = g

    def solve(self) -> int:
        """

        :param v:
        :param state:
        :return: -1 means INF
        """
        N = self.g.v_num
        dp = [[INT_INF for c in range(N)] for r in range(1 << N)]

        dp[(1 << N) - 1][0] = 0

        for state in range((1 << N) - 2, -1, -1):
            for v in range(N):
                for u in range(N):
                    if ((state >> u) & 1) == 0:
                        if dp[state | 1 << u][u] != INT_INF and self.g.edges[v][u] != INT_INF:
                            if dp[state][v] == INT_INF:
                                dp[state][v] = dp[state | 1 << u][u] + self.g.edges[v][u]
                            else:
                                dp[state][v] = min(dp[state][v], dp[state | 1 << u][u] + self.g.edges[v][u])
        return dp[0][0]


def main():
    V, E = map(int, input().split())
    g: Graph = Graph(V)
    for _ in range(E):
        src, dest, dist = map(int, input().split())
        g.setDist(src, dest, dist)

    tsp: TSPSolver = TSPSolver(g)
    print(tsp.solve())


if __name__ == "__main__":
    main()

Solution (Python):
import sys

V, E = map(int, sys.stdin.readline().strip().split())


edges = [[float("inf")]*V for i in range(V)]
for i in range(E):
   s, t, d = map(int, sys.stdin.readline().strip().split())
   edges[s][t] = d

dp = [[-1] * V for i in range(1<<V)]


def rec(bit, v):
    if dp[bit][v] >= 0:
        return dp[bit][v]

    if bit == (1<<V)-1 and v == 0:
        
        dp[bit][v] = 0
        return 0

    res = float("inf")
    for u in range(V):
        if not (bit>>u & 1):
            
            res = min(res,rec(bit|(1<<u), u) + edges[v][u])

    dp[bit][v] = res
    return res

res = rec(0, 0)
print(-1 if res == float("inf") else res)

Solution (Python):
def main():
  V, E = map(int, input().split())
  INF = float('INF')
  graph = [[] for _ in range(V)]
  for i in range(E):
    s, t, d = map(int, input().split())
    graph[s].append([t, d])
  dp = [[INF] * V for _ in range(1<<V)]
  dp[(1<<V)-1][0] = 0
  for bit in range((1<<V)-2, -1, -1):
    for v in range(V):
      for u, d in graph[v]:
        if not (bit>>u & 1):
          dp[bit][v] = min(dp[bit|1<<u][u]+d, dp[bit][v])

  if(dp[0][0] == INF):
    print(-1)
  else:
    print(dp[0][0])
  
if __name__ == '__main__':
	main()

Solution (Python):
import sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = 10**10
def I(): return int(input())
def F(): return float(input())
def S(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()

def resolve():
    V, E = LI()
    con = [[INF]*V for _ in range(V)]
    for _ in range(E):
        std = LI()
        con[std[0]][std[1]] = std[2]

    
    dp = [[INF]*V for _ in range(2**V)]
    
    dp[1][0] = 0
    visited = [[False]*V for _ in range(2**V)]

    def dfs(S, i):
        if not visited[S][i]:
            if S&1:
                Smi = S & ~(1<<i)
                for j in range(V):
                    if Smi>>j & 1:
                        tmp = dfs(Smi, j) + con[j][i]
                        if dp[S][i] > tmp:
                            dp[S][i] = tmp
            visited[S][i] = True

        return dp[S][i]

    for i in range(V):
        dfs(2**V-1, i)

    ans = min([dp[-1][i]+con[i][0] for i in range(V)])
    print(ans if ans<INF else -1)

if __name__ == '__main__':
    resolve()

Solution (Python):
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
def dp2(ini, i, j): return [[ini]*i for _ in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for _ in range(j)] for _ in range(k)]






V, E = mi()
rel = [[] for _ in range(V)]
inv_rel = [[] for _ in range(V)]
for i in range(E):
    s, t, c = mi()
    rel[s].append((t, c))
    

B = 2**V
dp = dp2(-1, V, B)


def rec_for(state, now):
    if dp[state][now] != -1:
        return dp[state][now]
    if state == B-1:
        dp[state][now] = 0
        return 0
    res = float('inf')
    for v, c in rel[now]:
        if v==0 and state|(1<<v)!=B-1:
            continue
        if not state & (1<<v):
            res = min(res, rec_for(state|(1<<v), v)+c)
    dp[state][now] = res
    return res


def rec_back(state, now):
    if dp[state][now] != -1:
        return dp[state][now]
    if state==now==0:
        dp[state][now] = 0
        return 0
    res = float('inf')
    for pv, c in inv_rel[now]:
        if pv==0 and state!=1:
            continue
        if state & (1<<pv):
            res = min(res, rec_back(state^(1<<pv), pv)+c)
    dp[state][now] = res
    return res

ans = rec_for(0, 0)

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

'''

dp = dp2(float('inf'), V, B)
dp[0][0] = 0

for state in range(B-1):
    for now in range(V):
        if dp[state][now] != float('inf'):
            for nv, c in rel[now]:
                
                    
                if not state & 1<<nv:
                    dp[state|(1<<nv)][nv] = min(dp[state|(1<<nv)][nv], dp[state][now]+c)

if dp[B-1][0] == float('inf'):
    print(-1)
    exit()
print(dp[B-1][0])
'''

Solution (Python):
V, E = map(int, input().split())
d = [[10 ** 9] * V for _ in range(V)]
dp = [[-1] * V for _ in range((1 << V))]
for i in range(E):
    s, t, di = map(int, input().split())
    d[s][t] = di

def rec(S, v, dp):
    
    if dp[S][v] >= 0: return dp[S][v]
    
    
    if (S == ((1 << V) - 1)) and v == 0:
        dp[S][v] = 0
        return 0
    res = 10 ** 9
    for u in range(V):
        
        if (S >> u & 1) == 0:
            
            
            res = min(res, rec(S + (1 << u), u, dp) + d[v][u])
    dp[S][v] = res
    return dp[S][v]

ans = rec(0, 0, dp)
print(ans if ans < 10 ** 9 else -1)

Solution (Python):
import math
import copy
import sys
import fractions


import decimal
import heapq
import collections
import itertools
import bisect



sys.setrecursionlimit(100001)







def getInputIntList():
    outputDataList = []
    inputData = input().split()
    outputDataList = [int(n) for n in inputData]

    return outputDataList


def getSomeInputInt(n):
    outputDataList = []
    for i in range(n):
        inputData = int(input())
        outputDataList.append(inputData)

    return outputDataList


def getSomeInputListInt(n):
    inputDataList = []
    outputDataList = []
    for i in range(n):
        inputData = input().split()
        inputDataList = [int(n) for n in inputData]
        outputDataList.append(inputDataList)

    return outputDataList




INF = sys.maxsize

v, e = map(int, input().split())
g = [[INF for _ in range(v)] for _ in range(1 << v)]

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

dp = [[INF for _ in range(v)] for _ in range(1 << v)]
dp[1][0] = 0

for bit in range(1, (1 << v) ):
    for i in range(v):
        if not bit>>i&1:
            continue

        for j in range(v):
            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(v):
    mn = min(mn, dp[(1 << v) - 1][end] + g[end][0])
if mn == INF:
    print(-1)
else:
    print(mn)

Solution (Python):
inf = 10**6
N, M = map(int, input().split())

edge = [[inf] * N for _ in range(N)]
for _ in range(M):
    s, t, c = map(int, input().split())
    edge[s][t] = c
for i in range(N):
    edge[i][i] = 0



dp = [[inf] * (1 << N) for _ in range(N)]
dp[0][0] = 0

for bit in range(1 << N):
    for t in range(N):
        if bit & (1 << t):
            continue
        bit_next = bit | (1 << t)
        for s in range(N):
            dp[t][bit_next] = min(dp[t][bit_next], dp[s][bit] + edge[s][t])


if dp[0][(1 << N)-1] >= inf:
    print(-1)
else:
    print(dp[0][(1 << N) - 1])

Solution (Python):



INF = float('inf')


def rec(bit, v):
    if dp[bit][v] != -1:
        return dp[bit][v]

    if (1 << V) - 1 == bit and v == 0:
        dp[bit][0] = 0
        return 0

    res = INF
    if v in D:
        for to, dist in D[v].items():
            if not (bit & (1 << to)):
                res = min(res, rec(bit | (1 << to), to) + dist)

    dp[bit][v] = res
    return res


if __name__ == "__main__":
    D = {}
    V, E = list(map(int, input().split()))
    for _ in range(E):
        s, t, d = list(map(int, input().split()))
        if s not in D:
            D[s] = {}
        D[s][t] = d

    dp = [[-1] * (V) for _ in range(1 << V)]

    print(dp[0][0] if rec(0, 0) != INF else -1)

Solution (Python):
ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))


v,e = mi()
sb = [[]for i in range(e)]
ub = [[]for i in range(e)]
w = [[float('inf')] * v for i in range(v)]
dp = [[-1] * v for i in range(2**v +1) ] 


for i in range(e):
    s,t,d = mi()
    sb[s].append(t)
    w[s][t] = d

def rec(s,p,dp):
    if dp[s][p] >0:
        return dp[s][p]
    
    if s == (1<<v)-1 and p == 0:
        dp[s][v-1] = 0
        return 0

    res = float('inf')
    for i in sb[p]:
        if (s >> i&1) == 0:
            a = rec(s|(1<<i), i,dp) + w[p][i]
            res = min(res, a)
    
    dp[s][p] = res
    return res

if v >= 3 and e >= 3:
    ans = rec(0,0,dp)
else:
    ans = -1

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

Solution (Python):
v, e = map(int, input().split())

dp = [[float("inf")] * (v) for _ in range(1 << v)]
edges = [[float("inf")] * v for _ in range(v)]


for edge in range(e):
    frm, to, w = map(int, input().split())
    edges[frm][to] = w

dp[1][0] = 0

for i in range(1 << v):
    for j in range(v):
        if dp[i][j] == float("inf"):
            continue
        for k in range(v):
            if (i >> k) % 2 == 1:
                continue
            next_d = dp[i][j] + edges[j][k]
            next_i = i | (1 << k)

            dp[next_i][k] = min(dp[next_i][k], next_d)

all = (1 << v) - 1
ans = float("inf")

for i in range(1, v):
    ans = min(ans, dp[all][i] + edges[i][0])

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

Solution (Python):
v,e=[int(j) for j in input().split()]
d=[[10**18]*v for i in range(v)]
dp=[[-1]*v for i in range(1<<v)]
for i in range(e):
    s,t,w=[int(j) for j in input().split()]
    d[s][t]=w


def f(s,n,dp):
    if dp[s][n]>=0:
        return dp[s][n]
    if s==(1<<v)-1 and n==0:
        dp[s][n]=0
        return 0
    tmp=10**18
    for u in range(v):
        if (s>>u&1)==0:
            tmp=min(tmp,f(s|(1<<u),u,dp)+d[n][u])
    dp[s][n]=tmp
    return tmp

ans=f(0,0,dp)
if ans==10**18:
    print(-1)
else:
    print(ans)

Solution (Python):
V, E = map(int, input().split())
graph = [[] for _ in range(V)]

for _ in range(E):
    s, t, d = map(int, input().split())
    graph[s].append((t, d))

case = 2**V
INF = 10**7

dp = [[-1]*case for _ in range(V)]

def dfs(now, dist, checked):
    if checked==(1<<V)-1:
        if now==s:
            return dist
        else:
            return INF
    r = dp[now][checked]
    if r!=-1:
        return r+dist
    ret = INF
    try:
        for q, d in graph[now]:
            if not (checked>>q)&1 and dist+d<ans:
                ret = min(ret, dfs(q, dist+d, checked|(1<<q)))
    except:
        return ret
    dp[now][checked] = ret - dist
    return ret

ans = INF

s = 0
ans = min(ans, dfs(0, 0, 0))

if ans<=10**6:
    print(ans)
else:
    print(-1)

Solution (Python):
v,e = map(int,input().split()) 
graph = [[] for i in range(v)]
cost = [[float('inf')]*v for i in range(v)]
for i in range(e):
    x,y,z = map(int,input().split())
    cost[x][y] = z
dp = [[float('inf')]*v for i in range(1<<v)]

dp[(1<<v)-1][0] = 0 
for i in range(2**v-2, -1, -1): 
    for j in range(v): 
        for k in range(v): 
            if i>>k & 1 != 1: 
                dp[i][j] = min(dp[i][j], dp[i|1<<k][k]+cost[j][k])
            
            
            
            
if dp[0][0] != float('inf'):
    print(dp[0][0]) 
else:
    print(-1)

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

def main():
	V, E = MAP()
	graph = [[] for _ in range(V)]
	for _ in range(E):
		s, t, d = MAP()
		graph[s].append((t, d))

	dp = [[INF]*V for _ in range(1<<V)]
	dp[(1<<V)-1][0] = 0
	for S in range((1<<V)-2, -1, -1):
		for v in range(V):
			for to, cost in graph[v]:
				if not ((S>>to) & 1):
					dp[S][v] = min(dp[S][v], dp[S|1<<to][to]+cost)
	if dp[0][0] != INF:
		print(dp[0][0])
	else:
		print(-1)

if __name__ == '__main__':
	main()

Solution (Python):
def main():
    inf = 1000000000
    n,m = map(int,input().split())
    d = [[inf]*n for _ in range(n)]
    for _ in range(m):
        a,b,c = map(int,input().split())
        d[a][b] = c
    dp = [[inf]*n for _ in range(1<<n)]
    dp[0][0] = 0
    for bits in range(1<<n):
        for i in range(n):
            if bits&(1<<i):continue
            for j in range(n):
                dp[(1<<i)|bits][i] = min(dp[(1<<i)|bits][i],dp[bits][j]+d[i][j])
    if dp[(1<<n)-1][0]==inf:print (-1)
    else                   :print (dp[(1<<n)-1][0])


if __name__ == '__main__':
    main()

Solution (Python):

import sys
import math
import string
import collections
import fractions
import random
from operator import itemgetter
import itertools
from collections import deque
import copy
import heapq
import bisect

MOD = 10 ** 9 + 7
INF = 10 ** 18
input = lambda: sys.stdin.readline().strip()

sys.setrecursionlimit(10 ** 8)


def solve():
    V, E = map(int, input().split())
    edges = [[INF] * V for _ in range(V)]

    for _ in range(E):
        s, t, d = map(int, input().split())
        edges[s][t] = d

    dp = [[INF] * (V + 1) for _ in range(2 ** V + 1)]
    dp[0][0] = 0
    for i in range(2 ** V):
        for j in range(V):
            for k in range(V):
                if (i >> k) & 1 == 0:
                    dp[i | (1 << k)][k] = min(dp[i | (1 << k)][k], dp[i][j] + edges[j][k])
    print(dp[2 ** V - 1][0] if dp[2 ** V - 1][0] != INF else -1)


if __name__ == "__main__":
    solve()

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

for i in range(e):
    frm, to, d = map(int, input().split())
    dis[frm][to] = d
  
mem = {}
end = 2**v-1

def minCost(state, pos):
    if state==end:
        return dis[pos][0]
    
    if (state,pos) in mem:
        return mem[(state, pos)]
    
    nxt = 1
    ret = INF
    
    for to in range(v):
        if 1<<to & state:
            continue
        
        ret = min(ret, minCost(state|1<<to, to) + dis[pos][to])
        
    mem[(state, pos)] = ret
    
    return ret

ans = minCost(1, 0)

if ans>=INF:
    print(-1)
else:
    print(ans)

Solution (Python):

from collections import defaultdict,deque
from heapq import heappush, heappop
from itertools import permutations
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n,m = LI()
    v = [[] for i in range(n)]
    for i in range(m):
        a,b,c = LI()
        v[a].append((b,c))

    B = 1<<n
    dp = [[float("inf")]*n for i in range(B)]
    for i,c in v[0]:
        dp[1<<i][i] = c
    for b in range(B):
        for i in range(n):
            if not b&(1<<i):
                continue
            for j,c in v[i]:
                if b&(1<<j):
                    continue
                nb = b|(1<<j)
                nd = dp[b][i]+c
                if nd < dp[nb][j]:
                    dp[nb][j] = nd
    ans = dp[B-1][0]
    if ans == float("inf"):
        print(-1)
    else:
        print(ans)
    return


if __name__ == "__main__":
    solve()

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools,queue

sys.setrecursionlimit(10**7)
INF = 20000
EPS = 1.0 / 10**10
MOD = 10**9+7

def LI(): return [int(x) for x in sys.stdin.readline().split()]

n, e = LI()
dist = [[INF for _ in range(n)] for _ in range(n)]
for _ in range(e):
    a,b,c = LI()
    dist[a][b] = c

dp = [[INF for _ in range(n)] for _ in range(1<<n)]

q = queue.Queue()

for i in range(1,n):
    if dist[0][i] < INF:
        dp[1 | (1<<i)][i] = dist[0][i]
        q.put((1 | (1<<i),i))

while not q.empty():
    bit, v = q.get()
    for u in range(1,n):
        if dist[v][u] < INF and not(bit & (1<<u)):
            next_bit = bit | (1<<u)
            if dp[next_bit][u]  == INF:
                q.put((next_bit, u))
            dp[next_bit][u] = min(dp[next_bit][u], dp[bit][v] + dist[v][u])

ans = INF
for i in range(1,n):
    ans = min(ans, dp[(1<<n)-1][i] + dist[i][0])
if ans < INF:
    print (ans)
else:
    print (-1)

Solution (Python):
num_V, num_E = map(int, input().split())
inf = float('inf')

d = [[inf] * num_V for _ in range(num_V)]

for _ in range(num_E):
	ts,tt,td = map(int, input().split())
	d[ts][tt] = td

dp = [[-1] * num_V for _ in range(1 << num_V)]

def solve(s,v,dp):
	if dp[s][v] >= 0:
		return dp[s][v]

	if s == ((1 << num_V) - 1) and v == 0:
		return 0

	tmp = inf
	for u in range(num_V):
		if s >> u & 1 == 0:
			tmp = min(tmp, solve(s|1 << u, u, dp) + d[v][u])

	dp[s][v] = tmp
	return dp[s][v]

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

Solution (Python):


def main():
    V, E = map(int, input().split())
    INF = float("inf")
    G = [[-1 for _ in range(V)] for _ in range(V)]

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

    
    dp = [[INF for _ in range(V)] for _ in range(1 << V)]
    
    dp[0][0] = 0



    for bit in range(1 << V):
        for curr in range(V):
            for nxt in range(V):
                
                if curr == nxt:
                    continue
                
                if bit & (1 << nxt):
                    continue
                
                if G[curr][nxt] == -1:
                    continue
                dp[bit | (1 << nxt)][nxt] = min(dp[bit | (1 << nxt)][nxt], dp[bit][curr] + G[curr][nxt])

    ans = dp[-1][0]
    print(ans if ans != INF else -1)
        
if __name__ == "__main__":
    main()