このシリーズではE869120さんによって作成された競プロ典型90問をPythonで解いています。
問題
ポイント
10人の選手の並べ方の総数は10! = 3628800通りです。
総当りで調べても十分時間内に間に合うので、噂になっている2人が並ばない組み合わせを全探索します。
pythonで並べ方の総数を全探索する際はitertools.permutationsを使うと便利です。
以上を踏まえ、実装したコードがこちらです。
尚、PythonだとTLEとなるためPyPyで提出しました。
コード
"""
10!が十分小さな値なので、全探索できる
険悪な関係をリストで所持しておき、全探索する際にチェックする
"""
def main():
import sys
import itertools
sys.setrecursionlimit(10 ** 9)
input = sys.stdin.readline
N = int(input())
A = [list(map(int, input().split(" "))) for _ in range(N)] # 各々の走る速さのリスト
M = int(input())
R = [[0 for _ in range(N)] for _ in range(N)] # 噂のリスト
# 不仲な噂を取得
for _ in range(M):
x, y = map(int, input().split(" "))
R[x-1][y-1] = R[y-1][x-1] = 1 # 不仲を1とする
ans = 10 ** 9
for p in list(itertools.permutations(range(N))):
tmp = 0
for i in range(len(p)):
tmp += A[p[i]][i] # p[i]番の選手が[i]番目の区画を走る時の速さ
if i < len(p)-1 and R[p[i]][p[i+1]] == 1: # 噂のチェック ※i < len(p) - 1 の条件を入れ忘れると index out of rangeとなるので注意
break
else:
if tmp < ans:
ans = tmp
print(ans if ans != 10 ** 9 else -1)
if __name__ == '__main__':
main()
