Question

Винни-Пух решил навестить своих друзей: Пятачка, Кролика и Иа-Иа. Ему обязательно нужно побывать у каждого из своих друзей и вернуться домой. Если он к кому-то не зайдет, то его друг обидится. Но вы же знаете Винни-Пуха: он не любит длительных путешествий. Помогите ему выбрать кратчайший путь, если известно, как расположены домики друзей и на каком расстоянии они находятся друг от друга

Answer 1

Алгоритм решения:
1. Построить граф, используя условие задачи, и расставить на нем расстояния.
2. Определить пары симметричных вариантов (симметричные варианты — это, например, пути В — К — — П — И — В   и   В — И — П — К — В) и вычеркнуть на графе один вариант из каждой пары.
3. Выписать оставшиеся варианты и подсчитать расстояния:
В — К — П — И — В = 60+ 50+ 55+ 30 = 195; В — К — И — П — В = 60+ 45+ 55+ 40 = 200;
В — И — К — П — В = 30+ 45+ 50+ 40 = 165.

Ответ: самый короткий путь Винни-Пуха: В — И — К — П — В= 165.