№1. Сумма дорог A–C и F–D, задача 1-04

№1

Сумма дорог A–C и F–D

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

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

Источник: ФИПИ (основная волна 19.06.2026), № 31139

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

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

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

from itertools import permutations

roads = 'AC AE AF BE BG CF CG DF DG'.split()
conns = ['47', '35', '246', '136', '267', '345', '15']
lens = [
    [0, 0, 0, 30, 0, 0, 2],
    [0, 0, 13, 0, 3, 0, 0],
    [0, 13, 0, 5, 0, 8, 0],
    [30, 0, 5, 0, 0, 39, 0],
    [0, 3, 0, 0, 0, 53, 21],
    [0, 0, 8, 39, 53, 0, 0],
    [2, 0, 0, 0, 21, 0, 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('A')][p.index('C')] + lens[p.index('F')][p.index('D')])
print(*ans)