The problem I'm solving right now is Exporter Tour in Baekjun Online Jersey #2098. I know that the most common way to solve this problem is through bitmask and dynamic programming. I planned it like that, but there's no output value at all. I want to know why there is no output value and how it is efficient to make a memo to solve the problem correctly.
# https://www.acmicpc.net/problem/2098
from math import inf
from sys import stdin,setrecursionlimit
setrecursionlimit(10**9)
def DP(now, visited):
global dpList, visitedAll,w
if now == 0:
#Initialize Start Point
if visited == 1:
dpList[now][visited] = 0
#Except for strange cases where there is more than 1 place already visited when the situation has started
else :
dpList[now][visited] = inf
if dpList[now][visited] != None:
pass
else:
#You haven't visited from here yet
tempVal = inf
visitedExceptNow = visited & (~now)
for i in range(n):
if (visitedExceptNow >> i) & 1:
before = i
tempVal = min(tempVal, DP(before,visitedExceptNow)+w[before][now])
dpList[now][visited] = tempVal
return dpList[now][visited]
n = int(stdin.readline())
w = list()
for _ in range(n):
w.append([inf if int(i) == 0 else int(i) for i in stdin.readline().split()])
dpList = [[None for _ in range(1 << n)] for __ in range(n)]
visitedAll = (1 << n) - 1
aList = list()
for i in range(1,n):
aList.append(DP(i,visitedAll)+w[i][0])
print(min(aList))
# https://www.acmicpc.net/problem/2098
# None and int cannot write min in the same list.
# Timeout number one
from sys import stdin
n = int(stdin.readline())
start = 0
visitedAll = (1 << n) - 1
w = [[] for _ in range(n)]
for i in range(n):
for j in map(int,stdin.readline().split()):
if j == 0:
w[i].append(None)
else :
w[i].append(j)
dpList = [[ -1 for _ in range(1 << n)] for __ in range(n)]
for j in range(1 << n):
if j == 1:
dpList[0][j] = 0
else :
dpList[0][j] = None
def DP(now: int, visited: int) -> int:
global dpList
if dpList[now][visited] == -1:
compareList = list()
visitedBefore = visited & (~(1 << now))
for i in range(visitedBefore):
if (visitedBefore >> i) & 1:
before = i
else:
continue
if DP(before, visitedBefore) is not None and w[before][now] is not None:
compareList.append(DP(before, visitedBefore)+w[before][now])
if compareList:
dpList[now][visited] = min(compareList)
else:
dpList[now][visited] = None
return dpList[now][visited]
else:
return dpList[now][visited]
endPointList = list()
for last in range(1,n) :
if DP(last, visitedAll) is not None and w[last][start] is not None:
endPointList.append(DP(last, visitedAll)+w[last][start])
print(min(endPointList))
It's a self-answer. Because of the lack of understanding of bitmask, you made the wrong recursive conditions.
© 2024 OneMinuteCode. All rights reserved.