Задание 1. Информатика. ЕГЭ. Шастин. 18.10.2024
- Просмотры: 182
- Изменено: 24 ноября 2024
(Д. Бахтиев) На рисунке справа схема дорог \(N\)-ского района изображена в виде графа, в таблице содержатся сведения о протяженности каждой из этих дорог (в километрах).
|
 |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Так как таблицу и схему рисовали независимо друг от друга, нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите, какова сумма протяжённостей дорог из пункта \(F\) в пункт \(E\) и из пункта \(E\) в пункт \(D\). В ответе запишите целое число.
Решение:
Python
from itertools import permutations
templ = {1: [4, 5], 2: [4, 8, 9], 3: [4, 5], 4: [1, 2, 3, 7, 9],
5: [1, 3, 6], 6:[5,], 7: [4, 8], 8: [2, 7], 9: [2, 4]}
s = 'AK BKD CKD DBCEGH EFD FEG GDFH HDG KBCA'
graph = {x[0]: set(x[1:]) for x in s.split()}
for p in permutations('ABCDEFGHK'):
d = {p[k-1]: set(p[i-1] for i in v) for k, v in templ.items()}
if d == graph:
print('1 2 3 4 5 6 7 8 9')
print(*p)
Вывод программы
1 2 3 4 5 6 7 8 9 B G C D K A E F H 1 2 3 4 5 6 7 8 9 C G B D K A E F H
\(FE = 8\), \(ED = 15\). Сумма протяжённостей дорог из пункта \(F\) в пункт \(E\) и из пункта \(E\) в пункт \(D\) равна \(8 + 15 = 23\).
Ответ: \(23\)