典型90 032 – AtCoder Ekiden（★3）

競プロの精進のために学びがあった問題についてまとめています。目標は AtCoder 水色！

今のレートは茶色です。

問題

考察

制約を考えたときに、N<=10であることから、Aijについても100未満となる。

もしすべての組み合わせについて全探索を行う場合は、10*10!があれば足りるため、 5秒の実行時間内に間に合いそうであることがわかる。

コード

import itertools

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

M = int(input())
XY = [[] for i in range(N+1)]
for i in range(M):
    x,y = map(int,input().split())
    XY[x].append(y)
    XY[y].append(x)


lst = [i for i in range(1, N+1)]
ans = pow(10, 18)

for lst2 in itertools.permutations(lst):
    t = 0
    f = True
    for i in range(N):
        r = lst2[i]
        if i > 0:
            l = lst2[i-1]
            if r in XY[l]:
                f = False
                break
            
        t += A[r-1][i]

    if f:
        ans = min(ans, t)

if ans == pow(10,18):
    print(-1)

else:
    print(ans)