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):
N, M = map(int, input().split())
INF = float('inf')
G = [[INF] * N for i in range(N)]
for i in range(M):
    s, t, d = map(int, input().split())
    G[s][t] = d


dp = [[INF] * N for i in range(1 << N)]
dp[1][0] = 0
for bs in range(1 << N):
    for n in range(N):
        if dp[bs][n] == INF:
            continue
        for to in range(N):
            if bs & (1 << to):
                continue
            next_index = bs | (1 << to)
            dp[next_index][to] = min(dp[next_index][to], dp[bs][n] + G[n][to])


ans = INF
for fr in range(1, N):
    ans = min(ans, dp[-1][fr] + G[fr][0])
print(ans if ans != INF else -1)

Solution (Python):


def memoize(f):
    table = {}
    def func(*args):
        if not args in table:
            table[args] = f(*args)
        return table[args]
    return func

@memoize
def tsp(p, v):
    if (1 << point_size) - 1 == v:
        return distance_table[p][0]
    else:
        return min(distance_table[p][x] + tsp(x, v | (1 << x)) for x in range(point_size) if not (v & (1 << x)))

from sys import stdin
from collections import defaultdict
from math import isinf

readline = stdin.readline

point_size, e = map(int, readline().split())
distance_table = [[float('inf')] * point_size for _ in range(point_size)]
for _ in range(e):
    s, t, d = map(int, readline().split())
    distance_table[s][t] = d
ans = tsp(0,1)
print(-1 if isinf(ans) else ans)

Solution (Python):
def read_list(t): return [t(x) for x in input().split()]
def read_line(t): return t(input())
def read_lines(t, N): return [t(input()) for _ in range(N)]

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

    ret = INF
    for to, cost in edge[v]:
        if not (state >> to & 1):
            ret = min(ret, rec(state | 1 << to, to) + cost)
    dp[state][v] = ret
    return ret

INF = 1<<27
V, E = read_list(int)
edge = [[] for _ in range(V)]
for _ in range(E):
    fr, to, cost = map(int, input().split())
    edge[fr].append((to, cost))

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

Solution (Python):
def read_list(t): return [t(x) for x in input().split()]
def read_line(t): return t(input())
def read_lines(t, N): return [t(input()) for _ in range(N)]

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

    ret = INF
    for to, cost in edge[v]:
        if not (state >> to & 1):
            ret = min(ret, rec(state | 1 << to, to) + cost)
    dp[state][v] = ret
    return ret

INF = float('inf')
V, E = read_list(int)
edge = [[] for _ in range(V)]
for _ in range(E):
    fr, to, cost = map(int, input().split())
    edge[fr].append((to, cost))

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

Solution (Python):
def read_list(t): return [t(x) for x in input().split()]
def read_line(t): return t(input())
def read_lines(t, N): return [t(input()) for _ in range(N)]

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

    ret = INF
    for to in range(V):
        if not (state >> to & 1):
            ret = min(ret, rec(state | 1 << to, to) + mat[v][to])
    dp[state][v] = ret
    return ret

INF = 1<<27
V, E = read_list(int)

mat = [[INF] * V for _ in range(V)]
for _ in range(E):
    fr, to, cost = map(int, input().split())
    mat[fr][to] = cost



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

Solution (Python):
def read_list(t): return [t(x) for x in input().split()]
def read_line(t): return t(input())
def read_lines(t, N): return [t(input()) for _ in range(N)]

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

    try:
        dp[state][v] = min(INF, min(rec(state | 1 << to, to) + cost for to, cost in edge[v] if not (state >> to & 1)))
    except:
        dp[state][v] = INF
    return dp[state][v]

INF = 1<<27
V, E = read_list(int)
edge = [[] for _ in range(V)]
for _ in range(E):
    fr, to, cost = map(int, input().split())
    edge[fr].append((to, cost))

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

Solution (Python):
def read_list(t): return [t(x) for x in input().split()]
def read_line(t): return t(input())
def read_lines(t, N): return [t(input()) for _ in range(N)]

INF = 1<<27
V, E = read_list(int)
edge = [[] for _ in range(V)]
for _ in range(E):
    fr, to, cost = map(int, input().split())
    edge[fr].append((to, cost))

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

Solution (Python):
import sys
readline = sys.stdin.readline
V, E = map(int, readline().split())
g = [[] for i in xrange(V)]
cost = {}
to = [0]*V
for i in xrange(E):
    s, t, d = map(int, readline().split())
    g[s].append((t, d))
    cost[s,t] = d
    to[s] |= 1 << t
get = cost.get
INF = 10**9
ALL = 2**V-1
dp = {}
start = 0
def dfs(state, v):
    key = (state, v)
    if key in dp: return dp[key]
    if state == ALL:
        dp[key] = res = get((v, start), INF)
        return res
    dp[key] = res = min((dfs(state | (1 << t), t) + d for t, d in g[v] if not state & (1 << t))) if state & to[v] != to[v] else INF
    return res
res = dfs(1, 0)
print res if res<INF else -1

Solution (Python):
v,e=map(int,raw_input().split())
dis=[[float("inf")]*v for _ in xrange(v)]
for i in xrange(e):
    s,t,d=map(int,raw_input().split())
    dis[s][t]=d
dp=[[float('inf')]*(v) for _ in xrange(1<<v)]
dp[1][0]=0
for i in xrange(1<<v):
    for j in xrange(v):
        if dp[i][j]==float('inf'):continue
        for k in xrange(v):
            if (i>>k)%2==1:continue
            nexti=i|1<<k
            nextdis=dp[i][j]+dis[j][k]
            dp[nexti][k]=min(dp[nexti][k],nextdis)
ans=float('inf')
for i in xrange(v):
    if dp[(1<<v)-1][i]==float('inf'):continue
    ans=min(ans,dp[(1<<v)-1][i]+dis[i][0])
if ans==float('inf'):
    print(-1)
else:
    print(ans)

Solution (Python):
from collections import defaultdict

v, e = map(int, input().split())

links = [set() for _ in range(v)]
bests = [None] * (1 << v)

for _ in range(e):
    s, t, d = map(int, input().split())
    links[s].add((t, d))

bests[0] = {0: 0}

for visited, best in enumerate(bests):
    if best is None:
        continue
    for last, cost in best.items():
        for t, d in links[last]:
            new_visited = visited | (1 << t)
            if visited == new_visited:
                continue
            new_best = bests[new_visited]
            if new_best is None:
                bests[new_visited] = defaultdict(lambda: 15001, [(t, cost + d)])
            else:
                new_best[t] = min(new_best[t], cost + d)

result = bests[-1]
print(-1 if result is None else -1 if result[0] == 15001 else result[0])

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

links = [set() for _ in range(v)]
bests = [[SENTINEL] * v for _ in range(1 << v)]

for _ in range(e):
    s, t, d = map(int, input().split())
    links[s].add((t, d))

bests[0][0] = 0

for visited, best in enumerate(bests):
    for last, cost in enumerate(best):
        for t, d in links[last]:
            bit = 1 << t
            if visited & bit:
                continue
            new_best = bests[visited | bit]
            new_best[t] = min(new_best[t], cost + d)

print(-1 if bests[-1][0] == 15001 else bests[-1][0])

Solution (Python):
v,e=map(int,raw_input().split())
dist=[[float("inf")]*v for _ in xrange(v)]
for i in xrange(e):
    s,t,d=map(int,raw_input().split())
    dist[s][t]=d

dp=[[float('inf')]*(v) for _ in xrange(1<<v)]
dp[1][0]=0
for i in xrange(1<<v):
    for j in xrange(v):
        if dp[i][j]==float('inf'):continue
        for k in xrange(v):
            if not (i>>k)&1:
                nexti=i|1<<k
                nextdist=dp[i][j]+dist[j][k]
                dp[nexti][k]=min(dp[nexti][k],nextdist)

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

Solution (Python):
N,e = map(int, input().split())
inf = float("inf")
adj = [[inf for _ in range(N)]  for _ in range(N)]
for _ in range(e):
    s,t,d = map(int, input().split())
    adj[s][t] = d

def memorize(f):
    cache = {}
    def func(*args):
        if args not in cache:
            cache[args] = f(*args)
        return cache[args]
    return func

@memorize
def tsp(v, b):
    if b == (1 << N) - 1:
        return adj[v][0]
    res = inf
    for w in range(N):
        if b & (1 << w): continue
        res = min(res, adj[v][w] + tsp(w, b | (1 << w)))
    return res

if tsp(0,1) == inf:
    print(-1)
else: print(tsp(0,1))

Solution (Python):
import sys

file_input = sys.stdin

V, E = map(int, file_input.readline().split())

no_route = 15001


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

adj = [[] for i in range(V)]

for line in file_input:
    s, t, d = map(int, line.split())
    if s == V - 1:
        
        dp[1 << t][t] = d
    else: 
        
        adj[t].append((s, d))


for b in range(1, 1 << (V - 1)):
    for i in range(V - 1):
        b_i = 1 << i
        if b & b_i:
            pre_bit = b ^ b_i
            dp_pre = dp[pre_bit]
            for s, d in adj[i]:
                pre_rec = dp_pre[s]
                if pre_rec != no_route:
                    dp[b][i] = min(dp[b][i], pre_rec + d)

ans = no_route


dp_comp = dp[(1 << (V - 1)) - 1]

for s, d in adj[V - 1]:
    comp_rec = dp_comp[s]
    if comp_rec != no_route:
        ans = min(ans, comp_rec + d)

if ans == no_route:
    print(-1)
else:
    print(ans)

Solution (Python):
def solve():
    V, E = map(int, input().split())
    edges = [[] for _ in [0]*V]
    for _ in [0]*E:
        s, t, d = map(int, input().split())
        edges[s].append((t, d))

    result = float("inf")
    beam_width = 80
    for i in range(V):
        q = [(0, i, {i})]
        for j in range(V-1):
            _q = []
            append = _q.append
            for cost, v, visited in q[:beam_width+1]:
                for dest, d_cost in edges[v]:
                    if dest not in visited:
                        append((cost+d_cost, dest, visited | {dest}))
            q = sorted(_q)
        for cost, v, visited in q[:beam_width+1]:
            for dest, d_cost in edges[v]:
                if dest == i:
                    if result > cost + d_cost:
                        result = cost + d_cost
                        break

    print(result if result < float("inf") else -1)


if __name__ == "__main__":
    solve()

Solution (Python):
def solve():
    V, E = map(int, input().split())
    edges = [[] for _ in [0]*V]
    for _ in [0]*E:
        s, t, d = map(int, input().split())
        edges[s].append((t, d))

    result = float("inf")
    beam_width = 70
    for i in range(V):
        q = [(0, i, {i})]
        for j in range(V-1):
            _q = []
            append = _q.append
            for cost, v, visited in q[:beam_width+1]:
                for dest, d_cost in edges[v]:
                    if dest not in visited:
                        append((cost+d_cost, dest, visited | {dest}))
            q = sorted(_q)
        for cost, v, visited in q[:beam_width+1]:
            for dest, d_cost in edges[v]:
                if dest == i:
                    if result > cost + d_cost:
                        result = cost + d_cost
                        break

    print(result if result < float("inf") else -1)


if __name__ == "__main__":
    solve()

Solution (Python):
def solve():
    V, E = map(int, input().split())
    edges = [[] for _ in [0]*V]
    for _ in [0]*E:
        s, t, d = map(int, input().split())
        edges[s].append((t, d))

    result = float("inf")
    beam_width = 66
    for i in range(V):
        q = [(0, i, {i})]
        for j in range(V-1):
            _q = []
            append = _q.append
            for cost, v, visited in q[:beam_width+1]:
                for dest, d_cost in edges[v]:
                    if dest not in visited:
                        append((cost+d_cost, dest, visited | {dest}))
            q = sorted(_q)
        for cost, v, visited in q[:beam_width+1]:
            for dest, d_cost in edges[v]:
                if dest == i:
                    if result > cost + d_cost:
                        result = cost + d_cost
                        break

    print(result if result < float("inf") else -1)


if __name__ == "__main__":
    solve()

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)

V, E = map(int, input().split())
INF = 10**9
G = [[] for _ in range(V)]
for _ in range(E):
    s, t, d = map(int, input().split())
    G[t].append((s, d))
def rec(bit, v):
    if dp[bit][v] != INF: return dp[bit][v]
    before = bit^(1<<v)
    for u, d in G[v]:
        if before&(1<<u):
            dp[bit][v] = min(dp[bit][v], rec(before, u)+d)
        if before == 0 and u == 0:
            dp[bit][v] = min(dp[bit][v], d)
    return dp[bit][v]

dp = [[INF]*V for _ in range(1<<V)]
ans = INF
ans = min(ans, rec((1<<V)-1, 0))
if ans != INF:
    print(ans)
else:
    print(-1)

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

inf = 10**7
edges = [[inf]*v for _ in range(v)]

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


dp = [[inf]*v for _ in range(2**v)]
dp[0][0] = 0


for x in range(2**v):
    
    for y in range(v):
        
        for z in range(v):
            
            if ((x >> y) & 1) and y != z and edges[z][y] < 10**6:
                dp[x][y] = min(dp[x][y], dp[x^(1<<y)][z]+edges[z][y])

if dp[-1][0] > 10**6:
    print(-1)
else:
    print(dp[-1][0])

Solution (Python):


INF = 10**9
n,e = map(int, input().split())
gl = [ [INF]*(n) for _ in range(n)]

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

dp = [ [INF]*(n) for _ in range(2**n) ]
dp[1][0] = 0
for i in range(2**n):
    for j in range(n):
        if dp[i][j] == INF: continue
        for k in range(n):
            if (i>>k)%2 == 1: continue
            dp[i|(1<<k)][k] = min(dp[i][j]+gl[j][k], dp[i|(1<<k)][k])

ans = INF
for i in range(1,n): 
    if gl[i][0] != INF:
        ans = min(ans, dp[2**n-1][i] + gl[i][0])

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

Solution (Python):

import sys
from collections import defaultdict

rl = sys.stdin.buffer.readline
INF = sys.maxsize

V, E = map(int, rl().split())
ES = [tuple(map(int, rl().split())) for i in range(E)]




G = defaultdict(lambda: defaultdict(lambda: INF))
for e in ES:
  G[e[0]][e[1]] = e[2]


dp = defaultdict(lambda: defaultdict(lambda: INF))
dp[0][0] = 0

for s in range(1 << V):
  for v in range(V):
    if s & (1 << v) == 0: 
      for u in range(V):
        dp[s | (1 << v)][v] = min(dp[s | (1 << v)][v], dp[s][u] + G[u][v])


print(dp[(1 << V) - 1][0] if dp[(1 << V) - 1][0] < INF else -1)

Solution (Python):
import sys
read = sys.stdin.read
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7


def main():
    V, E = map(int, readline().split())
    dist = [[INF] * V for _ in range(V)]
    for i in range(E):
        u, v, cost = map(int, readline().split())
        dist[u][v] = cost
    dp = [[-1] * V for _ 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 = 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

    ans = rec(0, 0, dp)
    if ans==INF:
        print(-1)
    else:
        print(ans)
if __name__ == '__main__':
    main()

Solution (Python):
from collections import defaultdict



n, w = map(int, input().split())

INF = 1 << 60
graph = defaultdict(lambda: INF)

for _ in range(w):
    a, b, c = map(int, input().split())
    graph[(a, b)] = c


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



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

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

    
    res = INF

    
    
    for u in range(n):
        if not (s >> u & 1):
            
            
            res = min(res, rec(s | (1 << u), u) + graph[(v, u)])

    dp[s][v] = res
    return dp[s][v]


ans = rec(0, 0)

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

Solution (Python):
n,w = map(int,input().split())


d = [[float("inf")]*n for i in range(n)]
for i in range(w):
   x,y,z = map(int,input().split())
   d[x][y] = z 


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



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

print(ans)

Solution (Python):
import sys
input = sys.stdin.readline
INF = float('inf')
N, M = map(int, input().split())
cost = [[INF]*N for _ in [0]*N]
to = [set() for _ in [0]*N]
for _ in [0]*M:
    a, b, c = map(int, input().split())
    cost[a][b] = c
    to[b].add(a)

K = 1 << N
dp = [[INF]*N for _ in range(K)]
dp[K-1][0] = 0

for bit in range(K-1, -1, -1):
    for i in range(N):
        tmp = [dp[bit|1<<j][j]+cost[j][i] for j in to[i] if bit>>j&1==0]
        if tmp:
            dist = min(tmp)
            if dp[bit][i] > dist:
                dp[bit][i] = dist

ans = dp[0][0]
print(ans if ans < INF else -1)

Solution (Python):
N,M=map(int,input().split())
L=[[]for i in range(N+1)]
for i in range(M):
    s,t,d=map(int,input().split())
    L[s].append([t,d])

D=[{}for i in range(N+1)]
D[0][(0,0)]=0



for i in range(1,N+1):
    for k,v in D[i-1].items():
        P,dist=k
        for to,d in L[P]:
            Ndist=dist|1<<to
            if Ndist!=dist:
                if (to,Ndist) not in D[i]:
                    D[i][(to,Ndist)]=v+d
                else:
                    D[i][(to,Ndist)]=min(v+d,D[i][(to,Ndist)])

if len(D[-1])==0:
    print(-1)
else:
    for k,v in D[-1].items():
        if k[0]==0:
            print(v)
            exit()
    print(-1)

Solution (Python):
def main():
    inf=float("inf")
    v,e=map(int,input().split())
    con=[{} for _ in range(v)]
    for _ in range(e):
        s,t,d=map(int,input().split())
        con[s][t]=d

    
    
    dp=[[inf]*(v-1) for _ in range(2**(v-1))]
    
    for x in con[0]:
        dp[2**(x-1)][x-1]=con[0][x]
    
    for i in range(1,2**(v-1)):
        if bin(i).count("1")==1 : continue
        for j in range(v-1):
            if not i>>j &1:continue
            work=i-2**j
            mn=inf
            for k in range(v-1):
                if not work>>k &1 : continue
                if not j+1 in con[k+1] : continue
                if dp[work][k]==inf : continue
                if mn>dp[work][k]+con[k+1][j+1]:
                    mn=dp[work][k]+con[k+1][j+1]
            dp[i][j]=mn
    
    mn=inf
    
    for i in range(v-1):
        if 0 in con[i+1]:
            if mn>con[i+1][0]+dp[2**(v-1)-1][i]:
                mn=con[i+1][0]+dp[2**(v-1)-1][i]



    if mn==inf : print(-1)
    else : print(mn)
    

main()

Solution (Python):
def solve():
  ans = 0
  V, E = map(int, input().split())
  edge = [[] for _ in range(V)]
  for i in range(E):
    s,t,d = map(int, input().split())
    edge[s].append([t,d])
  dp = [[float('inf')]*V for _ in range(1<<V)]
  for v,d in edge[0]:
    dp[1<<v][v] = min(dp[1<<v][v],d)
  for S in range(2,1<<V,2):
    for u in range(V):
      if (S>>u)&1:
        for v,d in edge[u]:
          if not (S>>v)&1:
            dp[S+(1<<v)][v] = min(dp[S+(1<<v)][v],dp[S][u]+d)
  return dp[-1][0] if dp[-1][0]<float('inf') else -1
print(solve())

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


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

def tsp(mask, pos):
  if mask == VISITED_ALL:
    return dist[pos][0]

  if dp[mask][pos] != -1:
    return dp[mask][pos]

  ans = float('inf')
  for city in range(V):
    if (1<<city)&mask == 0:
      newAns = dist[pos][city] + tsp(mask | (1<<city), city)
      ans = min(ans, newAns)

  dp[mask][pos] = ans
  return ans

res = tsp(1,0)
if res == float('inf'):
  print(-1)
else:
  print(res)

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

dp = [[INF for i in range(v)] for j in range(2**v)]

dp[0][0] = 0

for i in range(2**v):
    for j in range(v):
        for k , d in route[j]:
            if (i>>k) & 1 == 1:
                continue
            dp[i | (1<<k)][k] = min(dp[i | (1<<k)][k],dp[i][j] + d) 

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

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n, m = map(int, input().split())

    graph = [[f_inf] * n for _ in range(n)]
    for i in range(n):
        graph[i][i] = 0

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

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

    for S in range(1 << n):
        for v in range(n):
            for u in range(n):
                if ((1 << v) & S) == 0:
                    if v != u:
                        idx = S | (1 << v)
                        dp[idx][v] = min(dp[idx][v], dp[S][u] + graph[u][v])

    print(dp[-1][0] if dp[-1][0] != f_inf else -1)


if __name__ == '__main__':
    resolve()

Solution (Python):
INF=10**18
n,m=map(int,input().split())
dist=[[INF for _ in range(n)]for _ in range(n)]
dp=[[INF for _ in range(n+1)]for _ in  range(1<<n)]
for _ in range(m):
  a,b,c=map(int,input().split())
  dist[a][b]=c
dp[(1<<n)-1][0]=0
for bit in range((1<<n)-2,-1,-1):
  for v in range(n):
    for u in range(n):
      if not ((bit>>u) & 1):
        dp[bit][v]=min(dp[bit][v],dp[bit|1<<u][u]+dist[u][v])
print(dp[0][0] if dp[0][0]!=INF else -1)

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

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


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

def rec(s, v, dp):
    """
    s: 訪れた集合のbit演算（すべて訪れたら2**V-1になる）
    v: いまいる点
    dp: 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

ans = rec(0, 0, dp)

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

Solution (Python):


v, e = map(int, input().split())
n_l = [[float("Inf")] * v for y in range(v)]
for i in range(e):
    _s, _t, _d = map(int, input().split())
    n_l[_s][_t] = _d

ans = float("Inf")
dp = [[float("Inf")] * v for y in range(2**v)]
dp[1][0] = 0
for s in range(2**v):
    for i in range(v):
        if not((s>>i) & 1):
            continue
        _s = s & ~(1<<i)
        for j in range(v):
            if (_s>>j) & 1:
                dp[s][i] = min(dp[s][i], dp[_s][j] + n_l[j][i])

for i in range(v):
    ans = min(ans, dp[2**v-1][i] + n_l[i][0])
                
if ans != float("Inf"):
    print(ans)
else:
    print("-1")

Solution (Python):
def dp(S, v):
    if memo[S][v] != -1:
        return memo[S][v]
    if not S&(1<<v):
        memo[S][v] = inf
        return inf
    res = inf
    for i in range(n):
        if S&(1<<i) and d[i][v] != inf and i != v:
            res = min(res, dp(S&(~(1<<v)), i)+d[i][v])
    memo[S][v] = res
    return res

n, m = map(int, input().split())
inf = 10**10
d = [[inf for i in range(n)] for j in range(n)]
for i in range(m):
    s, t, dis = map(int, input().split())
    d[s][t] = dis

memo = [[-1 for i in range(n)] for j in range(2**n)]
memo[1][0] = 0

ans = min([dp(2**n-1, v)+d[v][0] for v in range(n)])
print(-1 if ans>=inf else ans)

Solution (Python):

INF = float('inf')
V, E = [int(x) for x in input().split()]
D = [[INF for _ in range(V)] for _ in range(V)]
for i in range(V):
    D[i][i] = 0
for j in range(E):
    s, t, d = [int(x) for x in input().split()]
    D[s][t] = d

dp = [[INF for _ in range(V)] for _ in range(1 << V)]
for S in range((1 << V) - 1, -1, -1):
    for v in range(V):
        if S == (1 << V) - 1:
            if v == 0:
                dp[S][v] = 0
        else:
            
            for u in range(V):
                if (S >> u) & 1 == 0:
                    dp[S][v] = min(dp[S][v], D[v][u] + dp[S + (1 << u)][u])

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

Solution (Python):

n,w = map(int,input().split())


d = [[float("inf")]*n for i in range(n)]
for i in range(w):
   x,y,z = map(int,input().split())
   d[x][y] = z 

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


def rec(s,v,dp):
    if dp[s][v] >= 0:
        return dp[s][v]
        
    if s == (1<<n)-1 and v == 0:
        
        dp[s][v] = 0
        return 0
    
    res = float("inf")
    for u in range(n):
        if (s>>u&1) == 0:
            

            res = min(res,rec(s|(1<<u),u,dp)+d[v][u])
            
    dp[s][v] = res
    return res

rec1=rec(0,0,dp)
if rec1==float("inf"):
    print(-1)
else:
    print(rec1)

Solution (Python):
V,E=map(int,input().split())
d=[[float('inf')]*V for _ in range(V)]
for i in range(E):
    com=list(map(int,input().split()))
    d[com[0]][com[1]]=com[2]
for i in range(V):
    d[i][i]=0
S=pow(2,V-1)
dp=[[0]+[float('inf')]*(S-1) for _ in range(V)]
for i in range(1,V):
    dp[i][1<<(i-1)]=d[0][i]
for i in range(1,S):
    for v in range(1,V):
        if i>>(v-1) & 1:
            
            
            dp[v][i]=min([float('inf')]+[dp[v][i]]+[dp[u][i-(1<<(v-1))]+d[u][v] for u in range(1,V) if i>>(u-1) & 1 and u!=v])
ans=min([dp[i][S-1]+d[i][0] for i in range(V)])
if ans==float('inf'):
    print(-1)
else:
    print(ans)

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

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

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

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 = float("inf")
	for u in range(V):
		if not s >> u&1:
			res = min(res, rec(s|(1<<u), u)+dis[v][u])
	
	dp[s][v] = res
	return res

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

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


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



dps = [[inf for _ in range(V)] for _ in range(1 << V)]

dps[0][0] = 0

for S in range(1, 1 << V):
    for i in range(V):
        
        
        
        if S & (1 << i) == 0:
            continue
        prev_bit = S - (1 << i)
        for j in range(V):
            
            dps[S][i] = min(dps[S][i], dps[prev_bit][j] + graphs[j][i])

if dps[(1 << V) - 1][0] == inf:
    print(-1)
else:
    print(dps[(1 << V) - 1][0])

Solution (Python):


import sys
sys.setrecursionlimit(10 ** 8)

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


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


def res(s, v):
    
    

    if dp[s][v] == -1:  
        return float('inf')
    elif dp[s][v] != float('inf'):
        return dp[s][v]
    elif (s >> v) & 1 == 0:  
        dp[s][v] = -1
        return float('inf')

    ans = float('inf')
    for u in range(V):
        
        
        
        ans = min(ans, res(s ^ (1 << v), u) + d[u][v])

    if ans == float('inf'):  
        dp[s][v] = -1
    else:
        dp[s][v] = ans

    return ans


res((1 << V) - 1, 0)



print(dp[-1][0])

Solution (Python):
import sys
import itertools

import time
import math
 
sys.setrecursionlimit(10 ** 7)
 
from collections import defaultdict
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

n,w = map(int,input().split())


d = [[float("inf")]*n for i in range(n)]
for i in range(w):
   x,y,z = map(int,input().split())
   d[x][y] = z 


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



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

Solution (Python):


import sys
sys.setrecursionlimit(10**7)

n,m=map(int,input().split())

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


dp=[[float('inf')]*n for i in range(2**n)]


dp[0][0]=0

def rec(bit,v):
    if dp[bit][v]!=float('inf'):
        return dp[bit][v]
    
    res=float('inf')
    
    prev_bit=bit&~(1<<v)
    
    for u,cost in G[v]:
        
        if prev_bit==0 and u==0:
            res=cost
            break
        if not (prev_bit&(1<<u)):
            continue
        
        res=min(res,rec(prev_bit,u)+cost)
    
    dp[bit][v]=res
    return dp[bit][v]

ans=rec(2**n-1,0)
if ans==float('inf'):
    print(-1)
else:
    print(ans)

Solution (Python):

V, E = map(int, input().split())
INF = 10**18
dist = [[INF] * V for _ in range(V)]
for _ in range(E):
  s, t, d = map(int, input().split())
  dist[s][t] = d
  


dp = [[INF] * V for _ in range(2**V)]


dp[0][0] = 0

for s in range(2**V):
  for j in range(V):
    if (s >> j & 1)==0:
      for i in range(V):
        if i != j:
          dp[s|1<<j][j] = min(dp[s|1<<j][j],dp[s][i]+dist[i][j])

print(-1) if dp[2**V-1][0] == INF else print(dp[2**V-1][0])