Задача #2214
Графы
(Е.Джобс) На рисунке справа схема дорог Н-ского района изображена в виде графа, в таблице содержатся сведения о длинах этих дорог (в километрах). Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. В таблице в левом столбце указаны номера пунктов, откуда совершается движение, в первой строке – куда. Определите номера пунктов E и С. Найденный номера перечислите в порядке убывания.
Войдите, чтобы история ответов и статистика сохранялись.
Решение
Ответ
42
Видео по задаче
# дороги из пунктов в порядке возрастания
# 346 из п1, 3456 из п2 и т.д.
gr = '347 3456 1245 1237 236 25 14'.split()
# дороги в графе
# из A в B, из A в C
roads = 'AB AC AD BC CD CE DE DF EF EG FG'.split()
from itertools import permutations
# перебираем все перестановки букв
for p in permutations('ABCDEFG'):
# формируем предполагаемое соответствие именам номеров
d = dict(zip(p, range(1, 8)))
# если все дороги на графе соответствуют дорогам из таблицы
if all(str(d[y]) in gr[d[x]-1]
for x, y in roads):
# выводим номера пунктов
print(d['C'], d['E'])