BOJ 10971外販員ツアー2

6184 ワード
2021.01.23 テキストリンク
https://www.acmicpc.net/problem/10971
2秒、256 MBメモリ
input :
  • N (2 ≤ N ≤ 10)
  • 費用行列(1<=成分<=10000、0には向かない)
  • W[i][j]都市iからjまでのコストは
    • である.
    入力
  • (常に巡回可能な場合)
    output :
  • 回の最低コスト出力
    • 条件:
  • 外販員は1つの都市から出発し、すべてのN都市を経て元の都市に戻るツアー旅行ルートを計画する.でも、もう一回行った町には行けない.
  • 最後の出発旅行に戻った都市を除く
  • 費用は非対称です.すなわち、W[i][j]はW[j][i]とは異なる場合がある.
    • はっきりしている.アルゴリズムの差は多くありませんが、毎回1つのものが漏れているので間違っています・・・
    開始ノードのみ(0～n-1)
    繰り返しのドアを回って、1人1つ選んで、全部チェックします.
    設定する条件.
    Data[now][next node]の値は0ではなく、next nodeはvisitでは使用できません.
    自分が0であることを指して、処理することができて、考えなくてもいいです.
    すべての状況を表示するには、dfsを実行するときと同様に、dfsが現れた後にvisitでpop()を使用する必要があります.
    また、最後のノードからstartノードへのパスが必要です.
    import sys
n = int(sys.stdin.readline())
data = []
for i in range(n):
    a = list(map(int, sys.stdin.readline().split()))
    data.append(a)


def dfs(start, now, total, visit):
    global ret
    if len(visit) == n:
        if data[now][start] != 0:
            ret = min(ret, total + data[now][start])
        return

    for j in range(n):
        if data[now][j] != 0 and j not in visit:
            visit.append(j)
            dfs(start, j, total + data[now][j], visit)
            visit.pop()


ret = 9999999
for i in range(n):
    dfs(i, i, 0, [i])

print(ret)
    各ノードで最小距離を求めて、最小のノードを見つけてみましたが、間違っていました.完全に探求すれば、すべてを回さなければなりません.
    kubernetes Controller
    1012号有機白菜