巡回セールスマン問題をbitDPで解く(Python)

Question

前提・実現したいこと

この巡回セールス問題をbitDpで解こうとしています。

問題：https://atcoder.jp/contests/typical-algorithm/tasks/typical_algorithm_c

やり方として、訪れた都市の状態管理をビットで表しています。
例：都市が８個の時、都市１と３のみ訪れたとすると
n = 00000101

発生している問題・エラーメッセージ

下記コードの26行目を消去したら答えがもとまったのですが、なぜ答えが出るようになったか理解できません。
私の考えでは、訪れた都市の状態(n)にそもそも”都市iを訪れた”情報がないと次の都市jに移動できないのではないかと考えています。

該当のソースコード

N = int(input())

A = [] #A[a][b]は都市aからbへいく時のコスト

for i in range(N):
    a = list(map(int, input().split()))
    A.append(a)

ALL = 1<<N
INF = 10**100

cost = []
for n in range(ALL): #訪れたとしが集合nで表され、最後に訪れたとしがiの時の総コスト
    cost.append([INF]*N)
cost[0][0] = 0

#重複してはいけないので、すでに訪れていないかのチェック。訪問済ならtrue
def _hasbit(n, i):
    return (n & (1 << i) > 0)

for n in range(ALL):
    for i in range(N):#移動元
        if _hasbit(n,i):#←消した箇所：訪れた集合のなかにしっかりとi番目の都市が含まれているか（i番目の都市が訪問済でなければ、そもそも移動できないのでは？）
            for j in range(N):#移動先
                if _hasbit(n,j) or i == j:#訪問済or移動元==移動先の時スキップ
                    continue
                cost[n| (1<< j)][j] = min(cost[n| (1 << j)][j], cost[n][i] + A[i][j])

print(cost[ALL-1][0])

試したこと

あらゆる箇所でデバッグプリントしましたが理解できませんでした…

補足情報（FW/ツールのバージョンなど）

Python3

Answer 1

cost[0][0] = 0

これだと最初の段階で都市0が未訪問だと判定されるのでifで弾くと次の都市に移動できません。
逆に未訪問の都市からスタートする不正なルートも無限大のコストがかかることになるので、一つでも正しいルートを通るパスが存在するならそれが最小コストになることはありません。