0У
Все задачи №1
№1

Длина дороги В–Д

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

АБВГДЕК
П1П2П3П4П5П6П7
П145
П24896
П3107
П411
П581112
П69101213
П756713

Источник: ФИПИ (открытый банк), № 29333

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

roads = 'АБ БВ БД ВГ ВД ВЕ ГЕ ДЕ ДК ЕК'.split()
conns = ['27', '1567', '67', '5', '246', '2357', '1236']
lens = [
    [0, 4, 0, 0, 0, 0, 5],
    [4, 0, 0, 0, 8, 9, 6],
    [0, 0, 0, 0, 0, 10, 7],
    [0, 0, 0, 0, 11, 0, 0],
    [0, 8, 0, 11, 0, 12, 0],
    [0, 9, 10, 0, 12, 0, 13],
    [5, 6, 7, 0, 0, 13, 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)