В далеком далеком будущем в Солнечной системе появится односторонняя (по каждой дороге можно проехать только в одну сторону) транспортная сеть, которая будет объединять 8 планет и…
В далеком далеком будущем в Солнечной системе появится односторонняя (по каждой дороге можно проехать только в одну сторону) транспортная сеть, которая будет объединять 8 планет и Плутон по следующему принципу: С Меркурия можно отправится на Венеру С Венеры можно отправится на Землю С Земли можно отправится на Меркурий и Марс С Марса можно отправится на Венеру, Юпитер и Нептун С Сатурна можно отправится на Плутон и Нептун С Урана можно отправится на Плутон С Непутна можно отправится на Уран С Плутона можно отправится на Нептун Сколько перелетов необходимо сделать на пути от Меркурия до Плутона?
Краткий ответ: 6 перелетов.
Пошаговое решение
- Запишем транспортную сеть как направленный граф (вершины — тела: Меркурий, Венера, Земля, Марс, Юпитер, Сатурн, Уран, Нептун, Плутон; ребра — допустимые направления полетов):
- Меркурий → Венера
- Венера → Земля
- Земля → Меркурий, Земля → Марс
- Марс → Венера, Марс → Юпитер, Марс → Нептун
- Сатурн → Плутон, Сатурн → Нептун
- Уран → Плутон
- Нептун → Уран
- Плутон → Нептун
Определим, какие пути ведут к Плутону. Плутон можно достичь из Сатурна или из Урана (Сатурн → Плутон, Уран → Плутон).
Определим, можно ли добраться до Сатурна или Урана из Меркурия:
- Из Меркурия можно пойти только в Венеру.
- Из Венеры можно пойти только в Землю.
- Из Земли можно пойти в Меркурий или в Марс.
- Из Марса можно попасть в Венеру, Юпитер или Нептун. Здесь важна только Нептун (чтобы попасть к Урану и затем к Плутону).
Далее по цепочке: из Марса можно попасть на Нептун, из Нептуна — в Уран, из Урана — в Плутон. Это даёт путь к Плутону.
Проверим кратчайший путь. Начальная часть обязана быть Меркурий → Венера → Земля (из Меркурия в другие направления идти нельзя). Затем из Земли — единственный полезный шаг к Плутону через Марс: Земля → Марс. Далее Марс → Нептун → Уран → Плутон.
Запишем сам путь и посчитаем перелеты: Меркурий → Венера → Земля → Марс → Нептун → Уран → Плутон Это 6 переходов (перелетов).
Ответ: 6 перелетов.
