提出 #57781928

---

ソースコード 拡げる

#A
# arr = input()
# if arr == '< < <':
#     print('B')
# elif arr == '< < >':
#     print('C')
# elif arr == '< > >':
#     print('A')
# elif arr == '> < <':
#     print('A')
# elif arr == '> > <':
#     print('C')
# else:
#     print('B')

#B
# import sys
# input = sys.stdin.readline
# N, M = map(int, input().split())
# dic = set()
# for i in range(M):
#     a, b = input().split()
#     if a not in dic and b == 'M':
#         print('Yes')
#         dic.add(a)
#     else:
#         print('No')


#C
import sys
input = sys.stdin.readline
import itertools
N = int(input())
MG = int(input())
graph = []
for i in range(MG):
    u, v = map(int, input().split())
    graph.append(tuple(sorted([u, v])))
MH = int(input())
graph2 = []
for i in range(MH):
    u, v = map(int, input().split())
    graph2.append(tuple(sorted([u, v])))
cost = [[None]*(N+1) for _ in range(N+1)]
for i in range(1, N):
    arr = list(map(int, input().split()))
    for j in range(i+1, N+1):
        cost[i][j] = arr[j-i-1]
# print(graph)
# print(graph2)
dots = [i for i in range(1, N+1)]
comb = itertools.permutations(dots, N)
comb = list(comb)
mincnt = 9999999999999999999


for i in comb:
    cnt = 0
    key = [0]+list(i)
    rkey = [0]*(N+1)
    for j in range(1, N+1):
        rkey[key[j]] = j
    tuned = []
    for road in graph2:
        first = key[road[0]]
        second = key[road[1]]
        if first > second:
            first, second = second, first
        tuned.append((first, second))

    for j in tuned:
        if j not in graph:
            one = rkey[j[0]]
            two = rkey[j[1]]
            if one > two:
                one, two = two, one
            cnt += cost[one][two]

    for j in graph:
        if j not in tuned:
            one = rkey[j[0]]
            two = rkey[j[1]]
            if one > two:
                one, two = two, one
            cnt += cost[one][two]
    if cnt < mincnt:
        mincnt = cnt
print(mincnt)

提出情報

ジャッジ結果