Atcoder 典型90問032 - AtCoder Ekiden（★3）[順列全探索][配列で隣接を評価]

■要約

　正直★3の中では今まで解いてきた問題で一番複雑だった．解き方はすぐに思いついた．Nがとても小さいので，①各区間の走り方の全パターンを考えて，②それぞれに対して噂話を評価して，区間にかかる時間を更新していけばよいと考えた．①については，pythonでは

num = list(range(N))
ptn = list(itertools.permutations(num)) 

のようにすれば，順列の各パターンを配列として作ってくれるので簡単である．(bit全探索のときとおなじ要領)．それに対し②に手こずった．答えを見たところ二次元配列を用意して，人xと人yがだめなペアだったら

grid[x][y]=False　のようにすれば良いことを知った．こういうのを思いつくようになりたい．

from sys import stdin
import itertools

N = int(input())
A = [list(map(int, stdin.readline().split())) for l in range(N)]
M = int(input())
temp = [list(map(int, stdin.readline().split())) for l in range(M)]
ans = 10**18

grid = [[True]*N for _ in range(N)]
#中が悪い組だけFalseにする
for i in range(M):
 grid[temp[i][0]-1][temp[i][1]-1] = False
 grid[temp[i][1]-1][temp[i][0]-1] = False

#走る順番のパターンを作成
num = list(range(N))
ptn = list(itertools.permutations(num)) 


#各パターンごとに条件を満たし，マラソンにかかる時間をもとめる
for p in ptn:
 cnt = 0
 Bool = True
 #for文の範囲がずれるからわざわざBoolで判定する
 for j in range(N-1): 
   if grid[p[j]][p[j+1]] == False:
     Bool = False
     break
 if Bool:
   for j in range(N):
     cnt += A[p[j]][j] #A[人][何区]
   ans = min(ans, cnt)
 #print("cnt", cnt)
 #ans = min(ans, cnt)
if ans == 10**18:
 print(-1)
else:
 print(ans)