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 math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools,queue

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

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

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

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

q = queue.Queue()

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

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

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

Submission status: Accepted

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

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

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

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

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

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

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

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

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

Submission status: Accepted

Solution code:


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

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

    # dp[bit][i] bitの１が立っている場所を訪問済みで、現在iにいる
    dp = [[INF for _ in range(V)] for _ in range(1 << V)]
    # 各所一回だけ訪問して一周できるなら、どこから始めても同じなので0のみ初期化
    dp[0][0] = 0



    for bit in range(1 << V):
        for curr in range(V):
            for nxt in range(V):
                # 現在地と次の場所が同じなら飛ばす
                if curr == nxt:
                    continue
                # 次行くところが既に訪問済みなら飛ばす
                if bit & (1 << nxt):
                    continue
                # 現在値から次の目的地にいけなければ飛ばす
                if G[curr][nxt] == -1:
                    continue
                dp[bit | (1 << nxt)][nxt] = min(dp[bit | (1 << nxt)][nxt], dp[bit][curr] + G[curr][nxt])

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

Submission status: Accepted

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

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

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

Submission status: Accepted

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

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

Submission status: Accepted

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

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

print(traveling_salesman(V,edge))

Submission status: Accepted

Solution code:
#!python3

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

from heapq import heappush, heappop

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

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

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

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

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

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

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

if __name__ == "__main__":
    resolve()

Submission status: Accepted

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

BIG_NUM = 2000000000
MOD = 1000000007
EPS = 0.000000001


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


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

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

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

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

#経路は輪になるので、スタートは0として良い
start = 0
dp = [[BIG_NUM]*V for _ in range(POW[V])]

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

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

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

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

Submission status: Accepted

Solution code:
# from scipy.sparse.csgraph import floyd_warshall
INF = 100000000


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

    # adj_listの初期化と入力
    for i in range(vertex):
        adj_list.append([])
        for j in range(vertex):
            if i == j:
                adj_list[i].append(0)
            else:
                adj_list[i].append(INF)
    for i in range(edge):
        s, t, cost = map(int, input().split())
        adj_list[s][t] = cost

    # dpの初期化
    for i in range(1 << vertex):
        dp.append([])
        for j in range(vertex):
            dp[i].append(-1)

    return adj_list, dp


def cal_min_cost(dp, vertex, edge, d, already, now_v):
    if dp[already][now_v] >= 0:
        # すでに通ったことがある場合
        return dp[already][now_v]

    if already == (1 << vertex) - 1 and now_v == 0:
        # 全ての頂点を通った
        dp[already][now_v] = 0
        return dp[already][now_v]

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


def main():
    vertex, edge = map(int, input().split())
    adj_list, dp = make_adj_list(vertex, edge)  # 初期化と入力
    # d = floyd_warshall(adj_list)  # それぞれの頂点からの最小を求める
    d = adj_list
    # for k in range(vertex):
    #     for i in range(vertex):
    #         for j in range(vertex):
    #             d[i][j] = min(d[i][j], d[i][k] + d[k][j])
    # print(d)
    # 最短距離は頂点のどこからはじめても変わらないので0からスタートとする
    min_cost = cal_min_cost(dp, vertex, edge, d, 0, 0)  # 計算
    if min_cost == INF:
        print(-1)
    else:
        print(int(min_cost))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import itertools
V, E = [int(_) for _ in input().split()]
STD = [[int(_) for _ in input().split()] for _ in range(E)]
G = [[float('inf')] * V for _ in range(V)]
for s, t, d in STD:
    G[s][t] = d
ans = float('inf')
dp = [[float('inf')] * V for _ in range(2**V)]
#for start in range(V):
for start in range(1):
    dp[(2**V - 1)][start] = 0
    for S in range(2**V - 1 - 2**start, -1, -1):
        for v in range(V):
            for u in range(V):
                if not (S >> u & 1):
                    dp[S][v] = min(dp[S][v], dp[S | 1 << u][u] + G[v][u])
    ans = min(ans, dp[0][start])
if ans == float('inf'):
    print(-1)
else:
    print(ans)
# http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_2_A&lang=jp

Submission status: Accepted

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

    # dp[bit_state][i] := すでにbit_stateの状態を訪れていて、
    #                     最後に訪問したのがi番目のときの最小値
    dp = [[INF]*n for i in range(1 << n)]
    dp[1 << 0][0] = 0
 
    for bit_state in range(1 << n):
        for i in range(n):
            # bit_stateにiを含んでいる
            if (bit_state >> i) & 1:
                for j in range(n):
                    # bit_stateにjを含んでいない
                    if not ((bit_state >> j) & 1):
                        dp[bit_state|(1 << j)][j] = min(dp[bit_state|(1 << j)][j], dp[bit_state][i] + matrix[i][j])
    ans = INF
    for i in range(n):
        ans = min(dp[(1 << n) - 1][i] + matrix[i][0], ans)
    return ans

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

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

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

Submission status: Accepted

Solution code:
import sys
from typing import List, Tuple


def rec(state: int, v: int, dp: List[List[int]],
        edges: List[List[Tuple[int, int]]]) -> int:
    if (dp[state][v] >= 0):
        return dp[state][v]
    if ((1 << V) - 1 == state and v == 0):
        # Reach all vertices and get back to the starting point.
        dp[state][0] = 0
        return 0

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


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

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys

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

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

# dp[bit][i] := 今iにいる時の、集合bitの最短距離
dp = list2d(1<<N, N, INF)
# 初期化：頂点0を開始位置として距離0にする
dp[1][0] = 0

for bit in range(1, (1<<N)-1):
    for i in range(N):
        # 頂点iが集合bitに含まれていない
        if not bit>>i&1: continue
        for j in range(N):
            # 頂点jは既に集合bitに含まれている
            if bit>>j&1: continue
            # 頂点iからjへの移動を遷移させる
            dp[bit+(1<<j)][j] = min(dp[bit+(1<<j)][j], dp[bit][i] + G[i][j])

mn=INF
for end in range(N):
    # 最後の頂点から戻ってくる分を足す
    mn = min(mn, dp[(1<<N)-1][end] + G[end][0])
if mn==INF:
    print(-1)
else:
    print(mn)

Submission status: Accepted

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

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


S = 0
dp = [[INF]*N for _ in range(1<<(N+1)-1)]
dp[0][S] = 0
for bit in range(1<<(N+1)-1):
    for s in range(N):
        now = dp[bit][s]
        for t,c in lines[s]:
            if bit & (1<<t): # 訪れたことがある
                continue
            else:
                dp[bit+(1<<t)][t] = min(dp[bit+(1<<t)][t],now+c)

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Permutation/Path - Traveling Salesman Problem
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_2_A&lang=jp

"""


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

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


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

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

Submission status: Accepted

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

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

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

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

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

Submission status: Accepted

Solution code:
dp = []
dist = []
INF = 1000000000

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

Submission status: Accepted

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

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

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)

Submission status: Accepted

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

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

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

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

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

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

Submission status: Accepted

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

#distance_list[j][i] = 頂点j→iの距離（有向）
distance_list = [[float('inf') for i in range(V)] for j in range(V)]
for i in range(V):
    distance_list[i][i] = 0
for node in range(E):
    start, goal, distance = map(int, input().split())
    distance_list[start][goal] = distance

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

Submission status: Runtime Error

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)