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|
s0 t0 d0
s1 t1 d1
:
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.

si and ti represent source and target vertices of i-th edge (directed) and di represents the distance between si and ti (the i-th edge).

Output

Print the shortest distance in a line. If there is no solution, print -1.

Constraints

 2 ≤ |V| ≤ 15
	

 0 ≤ di ≤ 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



Sample input:
4 6
0 1 2
1 2 3
1 3 9
2 0 1
2 3 6
3 2 4


Sample output:
16

Submission status: Accepted

Solution code:
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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys

file_input = sys.stdin

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

no_route = 15001

# (v-1) th vertex is excluded
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:
        # Record the distance from the (v-1) th vertex to the adjacent vertex
        dp[1 << t][t] = d
    else: 
        # Store distance from source, not target
        adj[t].append((s, d))

# DP
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

# A state where all vertices other than (v-1) have been visited.
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)

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
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[S][v]: 集合Sの中で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)

Submission status: Accepted

Solution code:
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は全体集合の部分集合Sについて最後がvであるという制約の下で順序を最適化したときのSの中での最小コスト
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):
            #1.すでに訪れたかどうか 2.最後に訪れたノードではないか 3. yとzはそもそもつながっているのか
            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])

Submission status: Accepted

Solution code:
# http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_2_A&lang=ja

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)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
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: # s に頂点v が含まれていないときを考える
      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)

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
from collections import defaultdict


# 頂点がn個, 辺がw個の場合
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

# -1でdpテーブルを初期化。bitで集合を管理するので1<<n（状態数） * n（curr）
dp = [[-1] * n for _ in range(1 << n)]


# 既に訪れた集合がs, curr=vの時に0に戻る最短経路を計算
def rec(s, v):
    # 既に計算されている場合はそのまま返す（メモ化再帰）
    if dp[s][v] >= 0:
        return dp[s][v]

    # 全ての頂点を訪問済みで、かつcurr=0の場合は0を返す
    if s == (1 << n) - 1 and v == 0:
        return 0

    # INFで初期化
    res = INF

    # sが現在の状態なので、1つずつ右シフトで読んでいく。未訪問（=0）の場合に処理
    # 最初は全て未訪問
    for u in range(n):
        if not (s >> u & 1):
            # 未訪問を1つずつ潰していくイメージ。uまで訪問していて、curr=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)

Submission status: Accepted

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

#d[i][j]:i→jへの距離
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)]


#訪れた集合がs、今いる点がvの時０に戻る最短経路
def rec(s,v,dp):
    if dp[s][v] >= 0:
        return dp[s][v]
        
    if s == (1<<n)-1 and v == 0:
        #全ての頂点を訪れた(s = 11...11 and v = 0)
        dp[s][v] = 0
        return 0
    
    res = float("inf")
    for u in range(n):
        if (s>>u&1) == 0:
            #uに訪れていない時(uの箇所が0の時),次はuとすると
            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)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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
#print(D)


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)])
#print(D)
if len(D[-1])==0:
    print(-1)
else:
    for k,v in D[-1].items():
        if k[0]==0:
            print(v)
            exit()
    print(-1)

Submission status: Accepted

Solution code:
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

    #最終的に閉路が得られる場合、結果はスタート地点によらないので0→0を考えればよい
    #ij成分はiのbitで表現された頂点0を含まない部分集合のうち、j番目の頂点で終わるものの最短経路長
    dp=[[inf]*(v-1) for _ in range(2**(v-1))]
    #initialize
    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
    #得られたグラフの終点と0をつなげられるか調べ最短距離を求める
    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)
    #print(dp)

main()

Submission status: Accepted

Solution code:
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())

Submission status: Accepted

Solution code:
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[mask][destination]
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)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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

# 2**V回、-1がV個の配列を作る
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]
    
    # すべて訪れており、かつ今いる点が0（始点）の場合
    if s == (1<<V)-1 and v == 0:
        dp[s][v] = 0
        return 0

    res = float('inf')
    for u in range(V):
    # まだuに訪れていないときuに訪れる。コストを再帰的に出す
        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)

Submission status: Accepted

Solution code:
# 49

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# テーブル埋め
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:
            # 次に行くuを決める
            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])

Submission status: Accepted

Solution code:

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

#d[i][j]:i→jへの距離
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)]

#訪れた集合がs、今いる点がvの時０に戻る最短経路
def rec(s,v,dp):
    if dp[s][v] >= 0:
        return dp[s][v]
        
    if s == (1<<n)-1 and v == 0:
        #全ての頂点を訪れた(s = 11...11 and v = 0)
        dp[s][v] = 0
        return 0
    
    res = float("inf")
    for u in range(n):
        if (s>>u&1) == 0:
            #uに訪れていない時(uの箇所が0の時),次はuとすると
#            print("s:",bin(s),"u:",u,"v:",v,"sp:",bin(s|(1<<u)),d[v][u])
            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)

Submission status: Accepted

Solution code:
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:
            #print(i,v)
            #print(*dp,sep='\n')
            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)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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
# print(graphs)


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):
        # 両方とも1のやつのみ残る。
        # 1100 と0100(1<<2)だったら0100になる。
        # 訪問済みであることがこれで確認できる。
        if S & (1 << i) == 0:
            continue
        prev_bit = S - (1 << i)
        for j in range(V):
            # print(S, prev_bit, i, j)
            dps[S][i] = min(dps[S][i], dps[prev_bit][j] + graphs[j][i])
# print(dps)
if dps[(1 << V) - 1][0] == inf:
    print(-1)
else:
    print(dps[(1 << V) - 1][0])

Submission status: Accepted

Solution code:
# DPL_2_A - 巡回セールスマン問題

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 初期化 -----------------
dp = [[float('inf')] * V for _ in range(1 << V)]  # 1 << V は 2 ** V に同じ
dp[0][0] = 0  # 頂点 0 からスタートするとする


def res(s, v):
    # s: すでに訪問した街の集合, v: 今いる街の集合, dp: 動的計画法のテーブル
    # 0 から出発して 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:  # 集合 s に頂点 v が含まれていないならば
        dp[s][v] = -1
        return float('inf')

    ans = float('inf')
    for u in range(V):
        # if (s >> u) & 1 == 1:
        # print(f's: {format(s ^ (1 << v), "b")}, u: {u}')
        # print(f'{d[u][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)

# for i in range(len(dp)):
#     print(dp[i])
print(dp[-1][0])

Submission status: Accepted

Solution code:
import sys
import itertools
# import numpy as np
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[i][j]:i→jへの距離
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)]


#訪れた集合がs、今いる点がvの時０に戻る最短経路
def rec(s,v):
    if dp[s][v] != -1:
        return dp[s][v]
        
    if s == (1<<n)-1 and v == 0:
        #全ての頂点を訪れた(s = 11...11 and v = 0)
        dp[s][v] = 0
        return 0
    
    res = float("inf")
    for u in range(n):
        if (s>>u&1) == 0:
            #uに訪れていない時(uの箇所が0の時),次はuとすると
            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)

Submission status: Accepted

Solution code:
#よくわからないがAC

import sys
sys.setrecursionlimit(10**7)

n,m=map(int,input().split())
#G[i]=iに来れるノード
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)]

#頂点0からとする
dp[0][0]=0
#0からbitを辿ってvに来る(vはSに入っている)
def rec(bit,v):
    if dp[bit][v]!=float('inf'):
        return dp[bit][v]
    
    res=float('inf')
    #Sからvを取る
    prev_bit=bit&~(1<<v)
    #print(bit,v,prev_bit)
    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)

Submission status: Accepted

Solution code:
# ハミルトン閉路はどこから初めても答えは変わらない
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[i][j]:= 状態i(2**V)にするための距離の最小値
# 最後に訪れたのがj
dp = [[INF] * V for _ in range(2**V)]

# 始点を0とする
dp[0][0] = 0

for s in range(2**V):# 現在の状態
  for j in range(V):# 次の頂点
    if (s >> j & 1)==0:# jが集合Sに含まれない
      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])

Submission status: Accepted

Solution code:
#標準入力
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
  
#print(dist)
#2 ** 15 = 1024 * 16 = 16384
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])
  #print(dp)

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

Submission status: Accepted

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