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:
# http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_2_A&lang=ja

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                                # どこにも訪れていない状態で、頂点0を出発点とする。
                                            # 最後に頂点0に戻ってくるために頂点0にフラグは立てないようにしている。

for S in range(1<<V):
    for v in range(V):
        if not (1<<v)&S:                    # vをすでに訪れている場合を除く
            dp[S|(1<<v)][v] = min(dp[S][u] + cost[u][v] for u in range(V))
                                            # "if (1<<u)&S" が必要に見えるが、Sにuが含まれないようなdpテーブルは、
                                            # dp[0][0]を除いて全てinfから動かない（漸化式の左辺に現れない）ので、自動的に除かれる。
                                            # 逆に、"if (1<<u)&S"を入れようとすると、初期化を"dp[1][0]=0"として、
                                            # かつ最後に頂点0に戻る場合を別に処理する必要があるので少し面倒。

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

Submission status: Accepted

Solution code:
def TS(G,v,e):
    INF = 16000
    DP = [[INF for _ in range(v)] for _ in range(2**v)]
    #DP[i][j]:訪問済みエリアのリストがiでjにいるような最短距離
    DP[0][0] = 0
    #   どれも訪問してない状態は00...0(長さv)として訪問済みを表現
    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()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

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)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

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

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

#dp[s][v]: 集合sを経由して今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:
            # i の箇所が訪れていないとき（0の時）次はiに行く
            # s|(1<<i) は、今まで訪れたsに加えて、頂点iをおとずれたことを加えた和集合
            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)

Submission status: Accepted

Solution code:
# https://www.slideshare.net/hcpc_hokudai/advanced-dp-2016 動的計画法の問題の解説がされている 神

# これが比較的わかりやすいかも https://algo-logic.info/bit-dp/

'''
定式化(本は"集める"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 #Vはあらゆる集合
dp[V][u] = INF #ほかはINFで初期化しておく

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

# verify https://onlinejudge.u-aizu.ac.jp/courses/library/7/DPL/all/DPL_2_A
INF = 2 ** 31
from itertools import product


def solve(n, graph):
    '''nは頂点数、graphは隣接行列形式'''
    max_S = 1 << n  # n個のbitを用意するため
    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:  # vが訪問済みの場合は飛ばす
                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 = 5
# graph = [[INF, 3, INF, 4, INF],
#          [INF, INF, 5, INF, INF],
#          [4, INF, INF, 5, INF],
#          [INF, INF, INF, 0, 3],
#          [7, 6, INF, INF, INF]]
# solve(n, graph)


# verify用
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)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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)] #dp[S][v]Sは訪れた町の集合vは今いる点

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

Submission status: Accepted

Solution code:
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):
            # print(bin(s), dist[(1<<i)|s][i], dist[s][j], i, j, G[j][i])
            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)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:

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

Submission status: Accepted

Solution code:
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[i][j] : i　はすでに訪れた集合, 現在いる状態から残りの全ての頂点を巡って頂点０に帰るようなパスの重みの最小値
    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()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys

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

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

# 訪れた集合がs、今いる点がvの時に、v=0に戻る最短経路
def rec(bit, v):
    if dp[bit][v] >= 0:
        return dp[bit][v]

    if bit == (1<<V)-1 and v == 0:
        #全ての頂点を訪れた(bit = 11...11 and v = 0)
        dp[bit][v] = 0
        return 0

    res = float("inf")
    for u in range(V):
        if not (bit>>u & 1):
            #uに訪れていない時(uの箇所が0の時),次はuとすると
            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)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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[S][i]: 集合Sを使ったiで終わるルートの最短コスト
    dp = [[INF]*V for _ in range(2**V)]
    # 0スタートに限定
    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()

Submission status: Accepted

Solution code:
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)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value
#from itertools import accumulate #list(accumulate(A))

## 4/25

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))
    #inv_rel[t].append((s, 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)
#ans = rec_back(B-1, 0)
if ans == float('inf'):
    print(-1)
    exit()
print(ans)

'''
# DP
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 nv == 0 and state|1 != B-1:
                    #continue
                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])
'''

Submission status: Accepted

Solution code:
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]
    # S == (1 << V) - 1はSを二進数表記したときに全てのbitが1であるかどうかを判定している
    # Sの全てのbitが1かつ、v(現在のノード)が0のときは、一周巡回したということになるので、dp[S][v]=0を設定する
    if (S == ((1 << V) - 1)) and v == 0:
        dp[S][v] = 0
        return 0
    res = 10 ** 9
    for u in range(V):
        # 集合Sを右シフトして左からu番目のbitが0の場合、到達していないノードという判定になるから、そのノードの最短経路を求めにいく
        if (S >> u & 1) == 0:
            # 集合Sに対して、今から調査するノードを整数で表すと(1 << u)となるので、S | (1 << u)を引数にする
            # ちなみにS >> u & 1 == 0であることが確定しているので、orだけじゃなくて加算しても動く
            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)

Submission status: Accepted

Solution code:
import math
import copy
import sys
import fractions
# import numpy as np
# import statistics
import decimal
import heapq
import collections
import itertools
import bisect

# from operator import mul

sys.setrecursionlimit(100001)


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

# ===FUNCTION===

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


# ===CODE===

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)

Submission status: Accepted

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


# 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])

Submission status: Accepted

Solution code:
# https://onlinejudge.u-aizu.ac.jp/problems/DPL_2_A


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)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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
# for i in range(V):
s = 0
ans = min(ans, dfs(0, 0, 0))

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

Submission status: Accepted

Solution code:
v,e = map(int,input().split()) #v:頂点, e:辺
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)]
#(1<<v)-1 == 2**v-1
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])
            #dp[i|1<<k]は「kを訪れた状態」を指す。
            #視点を変える。「今kにいる状態からゴールに至るのに必要なコスト」+「j→kに必要なコスト」は、
            #「今jにいる状態からゴールに至るのに必要なコスト」になる（遡る）
            #これを「今0にいる状態からゴールに至るのに必要なコスト」まで遡って計算する。
if dp[0][0] != float('inf'):
    print(dp[0][0]) #まだどこも訪れていない状態から、ゴールである0を目指して進む
else:
    print(-1)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#!usr/bin/env python3
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()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#!usr/bin/env python3
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

#Solve
if __name__ == "__main__":
    solve()