競プロ典型90問：032 - AtCoder Ekiden（★3）

問題

https://atcoder.jp/contests/typical90/tasks/typical90_af

挑戦結果

• 挑戦日：2021/10/07
• 結果：解けた
• 時間：20分ぐらい

考えたこと

• 全探索できそう。$10! = 3.6 * 10⁶$
• 順番の全列挙はpythonのライブラリにあったはず

公式解説

• https://twitter.com/e869120/status/1390074137192767489/photo/1

解説を読んだふりかえり

• pythonで投げたらTLEした。pypy3でAC。
• 方向性は問題なかった。
• 読者への課題のN<=18でも解けるアルゴリズムってなんだろう・・・。

ソース

from itertools import permutations

N = int(input())
A = []
for i in range(N):
    a = [int(x) for x in input().split()]
    A.append(a)

M = int(input())
# 嫌い合ってるペアをセットで持つ
P = set()
for _ in range(M):
    x,y = [int(x) for x in input().split()]
    x -= 1
    y -= 1
    P.add((x,y))
    P.add((y,x))

# 0～N-1 までの順番の全パターン
LL = permutations(range(N))

INF = float('inf')
ans = INF
# すべてのパターンから最短を探す
for L in LL:
    length = 0
    for i in range(N):
        if i+1<N and (L[i],L[i+1]) in P:
            length = INF
            break
        else:
            length += A[L[i]][i]
    ans = min(ans, length)

print(ans if ans < INF else -1)