№1. Длина дороги Г–К, задача 1-08

№1

Длина дороги Г–К

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

	П1	П2	П3	П4	П5	П6	П7
П1				5	4		6
П2			8	9		7
П3		8		12
П4	5	9	12
П5	4					13	11
П6		7			13		10
П7	6				11	10

Источник: ФИПИ (досрочная волна), № 28749

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

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

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

from itertools import permutations

roads = 'АБ АВ БВ БД ВЕ ГД ГЕ ГК ДК ЕК'.split()
conns = ['457', '346', '24', '123', '167', '257', '156']
lens = [
    [0, 0, 0, 5, 4, 0, 6],
    [0, 0, 8, 9, 0, 7, 0],
    [0, 8, 0, 12, 0, 0, 0],
    [5, 9, 12, 0, 0, 0, 0],
    [4, 0, 0, 0, 0, 13, 11],
    [0, 7, 0, 0, 13, 0, 10],
    [6, 0, 0, 0, 11, 10, 0],
]

ans = set()
for p in permutations('АБВГДЕК'):
    if all(str(p.index(x) + 1) in conns[p.index(y)] for x, y in roads):
        ans.add(lens[p.index('Г')][p.index('К')])
print(*ans)