Объяснение:

Это задача на поиск кратчайшего пути в графе. Будем использовать алгоритм Дейкстры или просто перебирать возможные пути, так как граф небольшой.

Таблица расстояний:

Поиск кратчайшего пути от A до F:

A -> C (1) -> B (1) -> D (3) -> E (1) -> F (5): 1 + 1 + 3 + 1 + 5 = 11
A -> C (1) -> B (1) -> D (3) -> F (6): 1 + 1 + 3 + 6 = 11
A -> C (1) -> D (6) -> E (1) -> F (5): 1 + 6 + 1 + 5 = 13
A -> C (1) -> D (6) -> F (6): 1 + 6 + 6 = 13
A -> B (2) -> C (1) -> ... (пути через B будут длиннее, чем через C, т.к. A->B=2, A->C=1)
A -> B (2) -> D (3) -> E (1) -> F (5): 2 + 3 + 1 + 5 = 11
A -> B (2) -> D (3) -> F (6): 2 + 3 + 6 = 11
A -> C (1) -> E (???) -> F (5): Нет прямого пути C -> E
A -> C (1) -> F (???): Нет прямого пути C -> F

От B (расстояние 2): B -> A (2+2=4, возврат), B -> C (2+1=3, уже есть короче), B -> D (расстояние 2+3=5)
Текущие расстояния: A=0, C=1, B=2, D=5

От D (расстояние 5): D -> B (5+3=8, длиннее), D -> C (5+6=11, длиннее), D -> E (расстояние 5+1=6), D -> F (расстояние 5+6=11)
Текущие расстояния: A=0, C=1, B=2, D=5, E=6, F=11

A -> C (1) -> B (1) -> D (3) -> F (6) = 1 + 1 + 3 + 6 = 11
A -> C (1) -> B (1) -> D (3) -> E (1) -> F (5) = 1 + 1 + 3 + 1 + 5 = 11
A -> C (1) -> D (6) -> E (1) -> F (5) = 1 + 6 + 1 + 5 = 13
A -> C (1) -> D (6) -> F (6) = 1 + 6 + 6 = 13
A -> B (2) -> D (3) -> E (1) -> F (5) = 2 + 3 + 1 + 5 = 11
A -> B (2) -> D (3) -> F (6) = 2 + 3 + 6 = 11
A -> C (1) -> E (???) -> F (5): Нет прямого пути C->E.
A -> C (1) -> F (???): Нет прямого пути C->F.
A -> B (2) -> E (???) -> F (5): Нет прямого пути B->E.
A -> B (2) -> F (???): Нет прямого пути B->F.

Из D: D -> F (6). Чтобы добраться до D, кратчайший путь A->C->B->D = 1+1+3=5. Итого: 5+6=11.
Из E: E -> F (5). Чтобы добраться до E, кратчайший путь A->C->B->D->E = 1+1+3+1=6. Итого: 6+5=11.

Ответ: 11

Поделись с друзьями