Задание 1 ЕГЭ по информатике 2027: схема дорог и таблица расстояний

import itertools

# рёбра схемы: дороги между пунктами, обозначенными буквами
edges = [('C', 'G'), ('C', 'H'), ('C', 'P'), ('E', 'F'),
         ('F', 'P'), ('F', 'S'), ('G', 'P')]

# таблица протяжённостей: пара номеров пунктов -> километры
length = {(1, 6): 25, (2, 3): 37, (2, 4): 60, (2, 6): 19,
          (3, 4): 97, (4, 7): 40, (5, 6): 39}


def neighbours(pairs):
    # вершина -> множество смежных с ней вершин
    adj = {}
    for a, b in pairs:
        adj.setdefault(a, set()).add(b)
        adj.setdefault(b, set()).add(a)
    return adj


graph = neighbours(edges)     # смежность на схеме
table = neighbours(length)    # смежность по таблице
letters = sorted(graph)

# перебираем все способы поставить буквам номера 1..7 и берём тот,
# при котором смежность на схеме и в таблице совпадает
match = None
for perm in itertools.permutations(range(1, 8)):
    m = dict(zip(letters, perm))
    ok = True
    for x in letters:
        for y in letters:
            if x != y and (y in graph[x]) != (m[y] in table[m[x]]):
                ok = False
    if ok:
        match = m
        break


def road(a, b):
    # протяжённость дороги между пунктами a и b по таблице
    x, y = match[a], match[b]
    return length.get((x, y)) or length.get((y, x))


print(road('C', 'G') + road('F', 'P'))

# рёбра схемы: дороги между пунктами, обозначенными буквами
edges = [('E', 'K'), ('E', 'M'), ('H', 'K'), ('H', 'P'),
         ('K', 'M'), ('M', 'N'), ('M', 'P')]

# таблица протяжённостей: пара номеров пунктов -> километры
length = {(1, 3): 51, (1, 6): 43, (2, 6): 20,
          (3, 5): 12, (4, 5): 99, (4, 6): 79, (5, 6): 26}


def neighbours(pairs):
    # вершина -> множество смежных с ней вершин
    adj = {}
    for a, b in pairs:
        adj.setdefault(a, set()).add(b)
        adj.setdefault(b, set()).add(a)
    return adj


graph = neighbours(edges)     # смежность на схеме
table = neighbours(length)    # смежность по таблице


def signature(v, adj):
    # «портрет» вершины: её степень и степени всех соседей
    return (len(adj[v]), tuple(sorted(len(adj[u]) for u in adj[v])))


# сопоставляем буквы номерам по совпадению «портретов»
match = {}
for letter in graph:
    for number in table:
        if signature(letter, graph) == signature(number, table):
            match[letter] = number


def road(a, b):
    # протяжённость дороги между пунктами a и b по таблице
    x, y = match[a], match[b]
    return length.get((x, y)) or length.get((y, x))


# путь E–M–P состоит из дорог E–M и M–P
print(road('E', 'M') + road('M', 'P'))

# рёбра схемы: дороги между пунктами, обозначенными буквами
edges = [('B', 'D'), ('D', 'F'), ('E', 'F'), ('F', 'T')]

# таблица протяжённостей: пара номеров пунктов -> километры
length = {(1, 2): 88, (1, 4): 71, (1, 5): 88, (3, 5): 45}


def neighbours(pairs):
    # вершина -> множество смежных с ней вершин
    adj = {}
    for a, b in pairs:
        adj.setdefault(a, set()).add(b)
        adj.setdefault(b, set()).add(a)
    return adj


graph = neighbours(edges)     # смежность на схеме
table = neighbours(length)    # смежность по таблице


def signature(v, adj):
    # «портрет» вершины: её степень и степени всех соседей
    return (len(adj[v]), tuple(sorted(len(adj[u]) for u in adj[v])))


# среди номеров ищем тот, чей «портрет» совпадает с портретом F
for number in sorted(table):
    if signature(number, table) == signature('F', graph):
        print(number)