Задание 1. Информатика. ЕГЭ. Шастин. 19.01.2025
- Просмотры: 486
- Изменено: 9 февраля 2025
(Л. Шастин) На рисунке схема дорог N-ского района изображена в виде графа, в таблице содержатся сведения о протяжённости каждой из этих дорог (в километрах)
|
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите на графе такие два напрямую друг с другом связанных пункта, расстояние между которыми максимально, и укажите в ответе их буквенные обозначения в алфавитном порядке. Например, если самая длинная дорога ведёт из \(E\) в \(A\), тогда в ответе следует указать \(AE\).
Решение:
Python
from itertools import permutations
graph = {'A': set('EH'),
'B': set('DEG'),
'C': set('HF'),
'D': set('BE'),
'E': set('ABD'),
'F': set('CG'),
'G': set('BFH'),
'H': set('ACG')}
templ = {1: [3, 8],
2: [5, 8],
3: [1, 4, 6],
4: [3, 6],
5: [2, 7],
6: [3, 4, 7],
7: [5, 6, 8],
8: [1, 2, 7]}
for p in permutations('ABCDEFGH'):
chk = {p[k-1]: set([p[i-1] for i in v]) for k, v in templ.items()}
if chk == graph:
print('1 2 3 4 5 6 7 8')
print(*p)
Вывод программы:
1 2 3 4 5 6 7 8 A C E D F B G H
Ответ: \(GH\)