032 - AtCoder Ekiden（★3） https://atcoder.jp/contests/typical90/tasks/typical90_af

typical90_af.py

from itertools import permutations

N = int(input())
A = [list(map(int, input().split())) for _ in range(N)]
M = int(input())
friends = [[True for _ in range(N)] for _ in range(N)]
for _ in range(M):
    x, y = map(lambda x: int(x) - 1, input().split())
    friends[x][y] = False  # x, yは仲が悪い
    friends[y][x] = False
ans = float("inf")
for lst in permutations(range(N)):
    sum = A[lst[0]][0]
    for i in range(1, N):
        if friends[lst[i - 1]][lst[i]] == False:
            break
        sum += A[lst[i]][i]
    else:
        ans = min(ans, sum)
print(-1 if ans == float("inf") else ans)