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: Wrong Answer

Solution code:
def dfs(g, last, vs, first):
    if vs:return min(g[last][v] + dfs(g, v, vs - {v}, first) for v in vs)
    else:return g[last][first]

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

readline = stdin.readline

v, e = map(int, readline().split())
g = [[float('inf')] * v for _ in range(v)]
for _ in range(e):
    s, t, d = map(int, readline().split())
    g[s][t] = d

cost = []
vs = set(range(v))
second = 0
for first in range(1, v - 1):
    if isinf(g[first][second]):continue
    for third in range(first + 1, v):
        if isinf(g[second][third]):continue
        cost.append(g[first][second] + g[second][third] + dfs(g, third, vs - {first,second,third}, first))
        
print(min(cost) if cost else -1)

Submission status: Wrong Answer

Solution code:
def dfs(g, last, vs, first):
    if vs:return min(g[last][v] + dfs(g, v, vs - {v}, first) for v in vs)
    else:return g[last][first]

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

readline = stdin.readline

v, e = map(int, readline().split())
g = [[float('inf')] * v for _ in range(v)]
for _ in range(e):
    s, t, d = map(int, readline().split())
    g[s][t] = d

cost = []
vs = set(range(v))

first = 0
for second in range(1, v):
    if isinf(g[first][second]):continue
    cost.append(g[first][second] + dfs(g, second, vs - {first,second}, first))
        
print(min(cost) if cost else -1)

Submission status: Wrong Answer

Solution code:
V, E = map(int, raw_input().split())
g = [[] for i in xrange(V)]
for i in xrange(E):
    s, t, d = map(int, raw_input().split())
    g[s].append((t, d))
INF = 1e9
dp = [[INF]*V for i in xrange(2**V)]
def dfs(state, v, cost, s):
    if state == 2**V-1:
        for t, d in g[v]:
            if t==s:
                return cost+d
        return INF
    if dp[state][v] != INF:
        return dp[state][v]
    res = INF
    for t, d in g[v]:
        if state & (1 << t):
            continue
        r = dfs(state | (1 << t), t, cost + d, s)
        res = min(res, r)
    dp[state][v] = res
    return res
res = min(dfs(0, v, 0, v) for v in xrange(V))
print res if res<INF else -1

Submission status: Wrong Answer

Solution code:
V, E = map(int, raw_input().split())
g = [[] for i in xrange(V)]
for i in xrange(E):
    s, t, d = map(int, raw_input().split())
    g[s].append((t, d))
INF = 1e9
dp = [[INF]*V for i in xrange(2**V)]
def dfs(state, v, s):
    if state == 2**V-1:
        return 0
    if dp[state][v] != INF:
        return dp[state][v]
    res = INF
    for t, d in g[v]:
        if state & (1 << t):
            continue
        r = dfs(state | (1 << t), t, s) + d
        res = min(res, r)
    dp[state][v] = res
    return res
res = min(dfs(0, v, v) for v in xrange(V))
print res if res<INF else -1

Submission status: Wrong Answer

Solution code:
V, E = map(int, raw_input().split())
g = [[] for i in xrange(V)]
for i in xrange(E):
    s, t, d = map(int, raw_input().split())
    g[s].append((t, d))
INF = 1e9
dp = [[INF]*V for i in xrange(2**V)]
def dfs(state, v, s):
    if state == 2**V-1:
        for t, d in g[v]:
            if t==s:
                return d
        return INF
    if dp[state][v] != INF:
        return dp[state][v]
    res = INF
    for t, d in g[v]:
        if state & (1 << t):
            continue
        r = dfs(state | (1 << t), t, s) + d
        res = min(res, r)
    dp[state][v] = res
    return res
res = min(dfs(1<<v, v, v) for v in xrange(V))
print res if res<INF else -1

Submission status: Wrong Answer

Solution code:
V, E = map(int, raw_input().split())
g = [[] for i in xrange(V)]
for i in xrange(E):
    s, t, d = map(int, raw_input().split())
    g[s].append((t, d))
INF = 1e9
dp = [[-1]*V for i in xrange(2**V)]
tmp = []
def dfs(state, v, s):
    if dp[state][v] != -1:
        return dp[state][v]
    if state == 2**V-1:
        for t, d in g[v]:
            if t==s:
                return d
        return INF
    res = INF
    for t, d in g[v]:
        if state & (1 << t):
            continue
        tmp.append(t)
        r = dfs(state | (1 << t), t, s) + d
        res = min(res, r)
        tmp.pop()
    dp[state][v] = res
    return res
res = min(dfs(1<<v, v, v) for v in xrange(V))
print res if res<INF else -1

Submission status: Wrong Answer

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 result[0])

Submission status: Wrong Answer

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 = 20
    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: Wrong Answer

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 = 40
    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: Wrong Answer

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 = 50
    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: Wrong Answer

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 = 60
    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: Wrong Answer

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 = 65
    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: Time Limit Exceeded

Solution code:
def dfs(g, last, vs, first):
    if vs:return min(g[last][v] + dfs(g, v, vs - {v}, first) for v in vs)
    else:return g[last][first]

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

readline = stdin.readline

v, e = map(int, readline().split())
g = [[float('inf')] * v for _ in range(v)]
for _ in range(e):
    s, t, d = map(int, readline().split())
    g[s][t] = d

cost = []
vs = set(range(v))

first = 0
for second in range(1, v):
    if isinf(g[first][second]):continue
    cost.append(g[first][second] + dfs(g, second, vs - {first,second}, first))
        
ans = min(cost) if cost else -1
print(-1 if isinf(ans) else ans)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
from math import isinf

readline = stdin.readline


min_cost = float('inf')


def main():
    v, e = map(int, readline().split())
    g = [[float('inf')] * v for _ in range(v)]
    for _ in range(e):
        s, t, d = map(int, readline().split())
        g[s][t] = d
    dfs(g, 0, 0, set(range(1, v)))
    global min_cost
    print(-1 if isinf(min_cost) else min_cost)


def dfs(g, cost, last, vs):
    global min_cost
    if min_cost < cost:
        return
    if vs:
        for v in vs:
            if isinf(g[last][v]):
                continue
            dfs(g, cost + g[last][v], v, vs - {v})
    elif min_cost > cost + g[last][0]:
        min_cost = cost + g[last][0]

main()

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
from collections import defaultdict
from math import isinf

readline = stdin.readline

def main():
    v, e = map(int, readline().split())
    g = [[float('inf')] * v for _ in range(v)]
    for _ in range(e):
        s, t, d = map(int, readline().split())
        g[s][t] = d
    from collections import deque
    min_cost = float('inf')

    que = deque()
    que.append((0, 0, set(range(1, v))))
    while que:
        cost, last, vs = que.pop()
        if min_cost < cost:
            continue
        if vs:
            que.extend((cost + g[last][v], v, vs - {v}) for v in vs)
        elif min_cost > cost + g[last][0]:
            min_cost = cost + g[last][0]

    print(-1 if isinf(min_cost) else min_cost)

main()

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
from collections import defaultdict
from math import isinf

readline = stdin.readline

min_cost = float('inf')

def main():
    v, e = map(int, readline().split())
    g = [[float('inf')] * v for _ in range(v)]
    for _ in range(e):
        s, t, d = map(int, readline().split())
        g[s][t] = d
    dfs(g, 0, 0, set(range(1, v)))
    global min_cost
    print(-1 if isinf(min_cost) else min_cost)


def dfs(g, cost, last, vs):
    global min_cost
    if min_cost < cost:
        return
    if vs:
        for v in vs:
            dfs(g, cost + g[last][v], v, vs - {v})
    elif min_cost > cost + g[last][0]:
        min_cost = cost + g[last][0]

main()

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
from collections import defaultdict
from math import isinf

readline = stdin.readline

min_cost = float('inf')

def main():
    v, e = map(int, readline().split())
    g = [[float('inf')] * v for _ in range(v)]
    for _ in range(e):
        s, t, d = map(int, readline().split())
        g[s][t] = d
    dfs(g, 0, 0, set(range(1, v)))
    global min_cost
    print(-1 if isinf(min_cost) else min_cost)


def dfs(g, cost, last, vs):
    global min_cost
    if min_cost <= cost:
        return
    if vs:
        for v in vs:
            dfs(g, cost + g[last][v], v, vs - {v})
    elif min_cost > cost + g[last][0]:
        min_cost = cost + g[last][0]

main()

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
from collections import defaultdict
from math import isinf

readline = stdin.readline

from collections import deque

def main():
    v, e = map(int, readline().split())
    g = [[float('inf')] * v for _ in range(v)]
    for _ in range(e):
        s, t, d = map(int, readline().split())
        g[s][t] = d
    min_cost = float('inf')

    que = deque([(0, 0, set(range(1, v)))])
    while que:
        cost, last, vs = que.pop()
        if min_cost <= cost:continue
        if vs:que.extend((cost + g[last][v], v, vs - {v}) for v in vs)
        elif min_cost > cost + g[last][0]:min_cost = cost + g[last][0]

    print(-1 if isinf(min_cost) else min_cost)

main()

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
from collections import defaultdict
from math import isinf

readline = stdin.readline

min_cost = float('inf')

def main():
    v, e = map(int, readline().split())
    g = [[float('inf')] * v for _ in range(v)]
    for _ in range(e):
        s, t, d = map(int, readline().split())
        g[s][t] = d
    dfs(g, 0, 0, set(range(1, v)))
    global min_cost
    print(-1 if isinf(min_cost) else min_cost)


def dfs(g, cost, last, vs):
    global min_cost
    if min_cost <= cost:return
    if vs:
        for v in vs:dfs(g, cost + g[last][v], v, vs - {v})
    elif min_cost > cost + g[last][0]:min_cost = cost + g[last][0]

main()

Submission status: Time Limit Exceeded

Solution code:
V, E = map(int, raw_input().split())
g = [[] for i in xrange(V)]
for i in xrange(E):
    s, t, d = map(int, raw_input().split())
    g[s].append((t, d))
INF = 10**9
dp = [[-1]*V for i in xrange(2**V)]
tmp = {}
def dfs(state, v, s):
    if dp[state][v] != -1:
        return dp[state][v]
    if state == 2**V-1:
        for t, d in g[v]:
            if t==s:
                dp[state][v] = d
                return d
        return INF
    res = INF
    idx = -1
    for t, d in g[v]:
        if state & (1 << t):
            continue
        r = dfs(state | (1 << t), t, s) + d
        if r < res:
            idx = t
        res = min(res, r)

    tmp[state, v] = (idx, res)

    return res
def solve(v):
    global dp
    dp = [[-1]*V for i in xrange(2**V)]
    return dfs(1<<v, v, v)
res = min(solve(v) for v in xrange(V))
print res if res<INF else -1

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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 = -1
def dfs(state, v):
    key = (state, v)
    if key in dp: return dp[key]
    if state == ALL:
        res = get((v, start), INF)
        dp[key] = res
        return res
    if state & to[v] != to[v]:
        res = min((dfs(state | (1 << t), t) + d for t, d in g[v] if not state & (1 << t)))
    else:
        res = INF
    dp[key] = res
    return res
def solve(v):
    global dp, start
    dp = {}
    start = v
    return dfs(1<<v, v)
res = min(solve(v) for v in xrange(V))
print res if res<INF else -1

Submission status: Time Limit Exceeded

Solution code:
import sys

def rec(p, V, bit, dist, matrix):
  if 2 ** V - 1 == bit and p == 0:
    return dist

  mindist = sys.maxint
  for i in range(V):
    if bit & 2 ** i == 0 and matrix[p][i] != sys.maxint:
      mindist = min(mindist, rec(i, V, bit | 2 ** i, dist + matrix[p][i], matrix))
  return mindist

ipt = raw_input().split()
V = int(ipt[0])
E = int(ipt[1])
s = {}
t = {}
d = {}
matrix = [[sys.maxint for i in range(V)] for j in range(V)]

for i in range(E):
  ipt = raw_input().split()
  matrix[int(ipt[0])][int(ipt[1])] = int(ipt[2])

ans = rec(0, V, 0, 0, matrix)
if ans == sys.maxint:
  print "-1"
else:
  print ans

Submission status: Time Limit Exceeded

Solution code:
import functools


@functools.lru_cache(maxsize=None)
def rec(state, v):
    if state == (1 << V) - 1 and v == 0:
        return 0
    ret = INF
    for c, w in edge[v]:
        if not (state >> c & 1):
            ret = min(ret, rec(state | 1 << c, c) + w)
    return ret

INF = 10**6
V, E = map(int, input().split())
edge = [[] for _ in range(V)]
for _ in range(E):
    s, t, w = map(int, input().split())
    edge[s].append((t, w))
ans = rec(0, 0)
print(ans if ans != INF else -1)

Submission status: Time Limit Exceeded

Solution code:
import functools


@functools.lru_cache(maxsize=None)
def rec(state, v):
    if state == (1 << V) - 1 and v == 0:
        return 0
    ret = INF
    for i, w in enumerate(A[v]):
        if not (state >> i & 1):
            ret = min(ret, rec(state | 1 << i, i) + w)
    return ret

INF = 10**6
V, E = map(int, input().split())
A = [[INF]*V for _ in range(V)]
for _ in range(E):
    s, t, w = map(int, input().split())
    A[s][t] = w
ans = rec(0, 0)
print(ans if ans != INF else -1)

Submission status: Time Limit Exceeded

Solution code:
# Acceptance of input
import sys

file_input = sys.stdin

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

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

for line in file_input:
    s, t, d = map(int, line.split())
    D[s].append((t, d))

max_d = 15001

# Full search with bit mask
def tsp(v, b):
    if b == (1 << V) - 1:
        if D[v]:
            t, d = min(D[v])
            if t == 0:
                return d
            else:
                return max_d
        else:
            return max_d
    res = max_d
    for t, d in D[v]:
        if b & (1 << t):
            continue
        res = min(res, d + tsp(t, b | (1 << t)))
    return res

# Output
ans = tsp(0, 1)

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

Submission status: Time Limit Exceeded

Solution code:
max_d = 15001

# Acceptance of input
import sys

file_input = sys.stdin

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

D = [[max_d] * V for i in range(V)]

for line in file_input:
    s, t, d = map(int, line.split())
    D[s][t] = d

# Full search with bit mask
def tsp(v, b):
    if b == (1 << V) - 1:
        return D[v][0]
    
    res = max_d
    for t, d in enumerate(D[v]):
        if b & (1 << t) or d == max_d:
            continue
        res = min(res, d + tsp(t, b | (1 << t)))
        
    return res

# Output
ans = tsp(0, 1)

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

Submission status: Time Limit Exceeded

Solution code:
# Acceptance of input
import sys

file_input = sys.stdin

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

max_d = 1001
adj = [[max_d] * V for i in range(V)]

for line in file_input:
    s, t, d = map(int, line.split())
    adj[s][t] = d

max_path = 15001
dp = [[max_path] * (1 << V) for i in range(V)]
dp[0][0] = 0

# Full search with bit mask
def tsp(v, b):
    if b == (1 << V) - 1:
        return None
    
    for t, d in filter(lambda x: x[1] != max_d, enumerate(adj[v])):
        if b & (1 << t):
            continue
        mask = b | (1 << t)
        t_d = dp[v][b] + adj[v][t]
        if dp[t][mask] > t_d:
            dp[t][mask] = t_d
            tsp(t, mask)

# Output
tsp(0, 0)

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

Submission status: Time Limit Exceeded

Solution code:
# Acceptance of input
import sys

file_input = sys.stdin

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

max_d = 1001
adj = [[max_d] * V for i in range(V)]

for line in file_input:
    s, t, d = map(int, line.split())
    adj[s][t] = d

max_path = 15001
dp = [[max_path] * (1 << V) for i in range(V)]
dp[0][0] = 0

# Full search with bit mask
def tsp(v, b):
    if b == (1 << V) - 1:
        return None
    
    for t, d in enumerate(adj[v]):
        if b & (1 << t) or d == max_d:
            continue
        mask = b | (1 << t)
        t_d = dp[v][b] + adj[v][t]
        if dp[t][mask] > t_d:
            dp[t][mask] = t_d
            tsp(t, mask)

# Output
tsp(0, 0)

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

Submission status: Time Limit Exceeded

Solution code:
# Acceptance of input
import sys

file_input = sys.stdin

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

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

for line in file_input:
    s, t, d = map(int, line.split())
    adj[s].append((t, d))

max_path = 15001
dp = [[max_path] * (1 << V) for i in range(V)]
dp[0][0] = 0

# Full search with bit mask
def tsp(v, b):
    if b == (1 << V) - 1:
        return None
    
    for t, d in adj[v]:
        if b & (1 << t):
            continue
        mask = b | (1 << t)
        t_d = dp[v][b] + d
        if dp[t][mask] > t_d:
            dp[t][mask] = t_d
            tsp(t, mask)

# Output
tsp(0, 0)

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

Submission status: Time Limit Exceeded

Solution code:
def solve():
    from heapq import heappop, heappush
    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")
    for i in range(V):
        q = [(0, i, {i})]
        while q:
            cost, v, visited = heappop(q)
            if len(visited) < V:
                for dest, d_cost in edges[v]:
                    if dest not in visited:
                        heappush(q, (cost+d_cost, dest, visited | {dest}))
            elif len(visited) == V:
                for dest, d_cost in edges[v]:
                    if dest == i:
                        heappush(q, (cost+d_cost, i, visited | {-1}))
            else:
                if result > cost:
                    result = cost
                break

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


if __name__ == "__main__":
    solve()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# http://www.geocities.jp/m_hiroi/light/pyalgo65.html

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)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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)
#edge = [[] for _ in range(V)]
mat = [[INF] * V for _ in range(V)]
for _ in range(E):
    fr, to, cost = map(int, input().split())
    mat[fr][to] = cost
#    edge[fr].append((to, cost))


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

Submission status: Accepted

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

Submission status: Accepted

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