Впишите в ответ число. Между населёнными пунктами A, B, C, D, E, F, Z построены дороги с односторонним движением.
Впишите в ответ число.
Между населёнными пунктами A, B, C, D, E, F, Z построены дороги с односторонним движением. В таблице указана протяжённость каждой дороги. Отсутствие числа в таблице означает, что прямой дороги между пунктами нет. Например, из А в В есть дорога длиной 4 км, а из В в А дороги нет.
Сколько существует таких маршрутов из А в Z, которые проходят через 6 и более населённых пунктов?
Пункты А и Z при подсчёте учитывать. Два раза проходить через один пункт нельзя.
Рассмотрим возможные маршруты:
A -> B -> C -> D -> E -> F -> Z
A -> B -> C -> D -> F -> E -> Z
A -> C -> D -> E -> F -> Z -> Z
Теперь проверим каждый маршрут:
A -> B (4) -> C (3) -> D (11) -> E (3) -> F (5) -> Z (2) = 28
A -> B (4) -> C (3) -> D (11) -> F (7) -> E (4) -> Z (10) = 39
A -> C (6) -> D (4) -> E (3) -> F (5) -> Z (2) = 20
Таким образом, существует 3 маршрута, которые проходят через 6 населенных пунктов.
Ответ: 3