Помните задачку из классной работы про транспортную сеть между планетами Солнечной системы (и Плутоном)? Так вот, за время, пока Вы добирались до домашки, она успела разрастись на…
Помните задачку из классной работы про транспортную сеть между планетами Солнечной системы (и Плутоном)? Так вот, за время, пока Вы добирались до домашки, она успела разрастись на всю Вселенную! Теперь она выглядит следующим образом: Из Млечного Пути можно добраться до Черной дыры Из Черной дыры можно попасть в центр Вселенной Из Андромеды можно попасть в Млечный Путь, Черную дыру, центр Вселенной, Большую медведицу, Альфа Центавру Из центра Вселенной можно попасть в Большую Медведицу из Большой медведицы можно попасть в Альфа Центавру Из Альфа Центавры можно попасть в Сириус и центр Вселенной Из Сириуса можно попасть в Млечный Путь, Черную дыру, Андромеду и центр Вселенной Напомним, что все дороги у этой транспортной сети односторонние. Сколько объектов придется посетить на своем пути, если мы хотим добраться из Млечного Пути до Андромеды самым коротким способом (сам Млечный Путь и Андромеда не учитываются) ?
Решение:
Построим кратко ориентированный граф (ребра указаны в условии): MW -> BH BH -> CoU CoU -> GB GB -> AC AC -> Sirius | CoU Sirius -> MW | BH | Andromeda | CoU Andromeda -> MW | BH | CoU | GB | AC
Чтобы попасть из Млечного Пути в Андромеду, смотрим возможные продолжения:
- MW может вести только в BH.
- BH может вести только в CoU.
- CoU может вести только в GB.
- GB может вести только в AC.
- У AC есть выбор: Sirius или CoU. Лучше выбрать Sirius, чтобы добраться до Андромеды (Sirius → Andromeda).
Следовательно,Shortest путь: MW → BH → CoU → GB → AC → Sirius → Andromeda.
Число посещённых объектов, если не считать Млечный Путь и Андромеду: BH, CoU, GB, AC, Sirius — всего 5 объектов.
Ответ: 5. Примечание: если считать количество переходов (ребер), получится 6 переходов, но количество промежуточных объектов равно 5.
