№1. Сумма дорог E–A и B–C, задача 1-01

№1

Сумма дорог E–A и B–C

На рисунке схема дорог изображена в виде графа, в таблице — длины этих дорог в километрах. Таблицу и схему рисовали независимо, поэтому нумерация пунктов в таблице никак не связана с буквами на графе. Определите, какова сумма длин дорог из пункта E в пункт A и из пункта B в пункт C. В ответе запишите целое число.

	П1	П2	П3	П4	П5	П6
П1		39			53	30
П2	39		21
П3		21		8	3
П4			8		13	5
П5	53		3	13
П6	30			5

Источник: ФИПИ (демоверсия), № 31498

Ответвпиши то, что вывела программа

Показать разбор

Выпиши дороги со схемы парами букв в roads, их тут 8. Проверь: в таблице столько же дорог.
Для каждой строки таблицы запиши номера соседей в conns, а сами длины перенеси в lens, пустые клетки замени нулём.
Перебери все расстановки букв по номерам через permutations и оставь те, где каждая дорога есть в таблице.
В подходящей расстановке найди номера нужных букв через p.index и возьми из lens сумму длин дорог E–A и B–C.
Расстановок может быть несколько, если схема симметричная. Складывай результат в множество: ответ у них должен быть один.

from itertools import permutations

roads = 'AE AF BC BD BE CF DE DF'.split()
conns = ['256', '13', '245', '356', '134', '14']
lens = [
    [0, 39, 0, 0, 53, 30],
    [39, 0, 21, 0, 0, 0],
    [0, 21, 0, 8, 3, 0],
    [0, 0, 8, 0, 13, 5],
    [53, 0, 3, 13, 0, 0],
    [30, 0, 0, 5, 0, 0],
]

ans = set()
for p in permutations('ABCDEF'):
    if all(str(p.index(x) + 1) in conns[p.index(y)] for x, y in roads):
        ans.add(lens[p.index('E')][p.index('A')] + lens[p.index('B')][p.index('C')])
print(*ans)