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

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

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

ABCDEF
A 912416
B9 5248
C5 2103
D1222 85
E44108 
F16835 

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

Решение:

Python


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


W = ((0, 9, 0, 12, 4, 16),
     (9, 0, 5, 2, 4, 8),
     (0, 5, 0, 2, 10, 3),
     (12, 2, 2, 0, 8, 5),
     (4, 4, 10, 8, 0, 0),
     (16, 8, 3, 5, 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, 'A', 'F'))

Ответ: \(15\)