競プロ精進ログ

典型90 032 – AtCoder Ekiden(★3)

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

今のレートは茶色です。

問題

典型90 032 - AtCoder Ekiden(★3)を解きました。

考察

制約を考えたときに、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)

まとめ

全探索のための列挙を再帰関数で実装しようとしてかなり手間取りました。

結果的にただの順列列挙ということに気づいてACできました。

あと、2次配列の添え字の位置を間違えていたせいでWAが出てかなりイラつきました。(問題ちゃんと読め)

COMMENT

メールアドレスが公開されることはありません。