外审员巡回

コード#コード#

n = int(input())
inf = float('inf')
data = [list(map(int, input().split())) for _ in range(n)]
dp = [[inf for _ in range(1 << n)] for _ in range(n)]


def dfs(x, visited):  # x : 현재 방문한 노드, visited : 지금까지 방문 노드를 담고있는 기록
    if dp[x][visited] != inf:  # 겪은 상황일 경우
        return dp[x][visited]

    if visited == (1 << n) - 1:  # 모든 노드를 방문한 경우
        if data[x][first] != 0:  # 다시 최초 출발지로 돌아가야 한다. x -> first
            return data[x][first]
        else:
            return inf

    min_val = inf
    for to in range(n):  # 전체 노드 방문
        if to == first:  # 최초 출발지는 제외
            continue
        if data[x][to] == 0:  # x->to의 길이 없는 경우 제외
            continue
        if visited & (1 << to) != 0:  # 방문기록에 존재하는 지점(to)은 제외
            continue
        min_val = min(min_val, data[x][to] + dfs2(to, visited | (1 << to)))

    dp[x][visited] = min_val
    return min_val


first = 2  # 최초 출발지 0 ~ n-1 중 임의의 노드를 선택 (무엇을 선택해도 결과는 같다)
print(dfs(first, 2 ** first))

方法

dfs->フルパスナビゲーション

dp->注釈作成(理由:時間の複雑さ)

ビットマスク->dp(理由:空間的複雑さ)

dp[0][011]の意味

現在アクセスしているノードは0

です

現在の状態では、アクセスレコードは0111です.(0111は2進数、10進数で7)

0111
^3번 노드의 방문 여부를 나타낸다. (0이므로 아직 방문하지 않은 상태)
0111
 ^2번 노드의 방문 여부를 나타낸다. (1이므로 방문한 상태)
0111
  ^1번 노드의 방문 여부를 나타낸다. (1이므로 방문한 상태)
0111
   ^0번 노드의 방문 여부를 나타낸다. (1이므로 방문한 상태)

dp[0][0111] (== dp[0][7])►現在のアクセスノードが0、アクセスレコードが0111(7)の場合、すべての場合のコストが最も低くなります.
まず、現在のアクセスノードは0、アクセスレコードは0111
これは,以前にアクセスしたノードが1,2であることを意味する.
この場合、可能な経路は1->2->0または2->1->0である.
上記可能な経路のうち、最も費用のかかる経路はdp[0][0111]に記録される.

dp[0][011]注釈されるプロセス

...

def dfs(x, visited):  
    # 현재 방문한 노드는 x, 현재까지 방문기록은 visited이다.
    
    ...
    
    min_val = inf
    for to in range(n):  # 전체 노드 방문
        ...
        # for 문에서 방문이 가능한 노드들을 고른다. 
        # "x(현재노드) -> to(그 다음 방문노드) -> ... -> 최초 방문 노드" 
        # 의 비용을 나타내는 코드가 
        # data[x][to] + dfs2(to, visited | (1 << to) 이 부분이다.
        min_val = min(min_val, data[x][to] + dfs2(to, visited | (1 << to)))
        
    # 현재 방문한 노드는 x, 현재까지의 방문 기록이 visited인 상황에서 
    # 위 for문을 통해 가능한 모든 경로를 계산하여 그 중 최소 비용이 min_val 변수에 담겨있다.
    # 이를 dp[x][visited]에 메모한다.
    dp[x][visited] = min_val
    return min_val

...

ポイントは、dp[x][visited]がすべての可能な経路計算後の最低費用を含んでいることです.

ビットマスクによる集約演算