Задание 4. Информатика. ОГЭ. Ушаков 2025-17

Просмотры: 65
Изменено: 1 февраля 2025

Между населёнными пунктами \(A, \, B, \, C, \, D, \, E, \, F\) построены дороги, протяжённость которых (в километрах) приведена в таблице.

ABCDEF
A 611217
B 94122
C69 4312
D1144 66
E21236 
F172126 

Определите длину кратчайшего пути между пунктами \(A\) и \(F,\) проходящего через пункт \(C.\) Передвигаться можно только по дорогам, протяжённость которых указана в таблице, два раза посещать один пункт нельзя.

Решение:

Python


def dfs(graph, beg, end, vis = set(), cur = 0):
    vis.add(beg)
    if beg == end:
        return vis, cur
    min_len = 10**100
    vtmp = None
    for town, dist in graph[beg]:
        if town not in vis:
            v, ml = dfs(graph, town, end, vis | {town}, cur + dist)
            if ml < min_len:
                min_len, vtmp = ml, v
    return vtmp, min_len

W = ((0, 0, 6, 11, 2, 17),
     (0, 0, 9, 4, 12, 2),
     (6, 9, 0, 4, 3, 12),
     (11, 4, 4, 0, 6, 6),
     (2, 12, 3, 6, 0, 0),
     (17, 2, 12, 6, 0, 0))

towns = 'ABCDEF'

G = {towns[i]: [(towns[j], v) for j, v in enumerate(W[i]) if v] for i in range(len(W))}

print(dfs(G, 'C', 'F', *dfs(G, 'A', 'C'))[1])

Ответ: \(17\)