№1. Сумма дорог G–F и C–B, задача 1-11

№1

Сумма дорог G–F и C–B

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

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

Источник: ФИПИ (пересдача 03.07.2025), № 23547

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

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

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

from itertools import permutations

roads = 'AF AG BC BD BE CD CF EG FG'.split()
conns = ['24', '134', '267', '125', '47', '37', '356']
lens = [
    [0, 21, 0, 8, 0, 0, 0],
    [21, 0, 39, 2, 0, 0, 0],
    [0, 39, 0, 0, 0, 53, 5],
    [8, 2, 0, 0, 13, 0, 0],
    [0, 0, 0, 13, 0, 0, 3],
    [0, 0, 53, 0, 0, 0, 30],
    [0, 0, 5, 0, 3, 30, 0],
]

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