Дороги в стране Жадного Короля платные. Помоги Путешественнику добраться от Рынка до Замка, заплатив меньше всего денег. Сколько он потратит?

Решение:

Это задача на нахождение кратчайшего пути в графе. Нам нужно найти путь от Рынка (изображен слева, с фруктами и тележками) до Замка (изображен справа), минимизируя суммарную стоимость проезда по дорогам.

Рассмотрим все возможные пути и их стоимость:

• Путь 1: Рынок → Верхняя дорога (4p) → Средняя дорога (2p) → Верхняя дорога к замку (10p) = 4 + 2 + 10 = 16p
• Путь 2: Рынок → Верхняя дорога (4p) → Средняя дорога (2p) → Нижняя дорога к замку (8p) = 4 + 2 + 8 = 14p
• Путь 3: Рынок → Средняя дорога (12p) → Верхняя дорога к замку (10p) = 12 + 10 = 22p
• Путь 4: Рынок → Средняя дорога (12p) → Нижняя дорога к замку (8p) = 12 + 8 = 20p
• Путь 5: Рынок → Средняя дорога (12p) → Центральная дорога (2p) → Верхняя дорога к замку (10p) = 12 + 2 + 10 = 24p
• Путь 6: Рынок → Средняя дорога (12p) → Центральная дорога (2p) → Нижняя дорога к замку (8p) = 12 + 2 + 8 = 22p
• Путь 7: Рынок → Нижняя дорога (2p) → Средняя дорога (5p) → Центральная дорога (2p) → Верхняя дорога к замку (10p) = 2 + 5 + 2 + 10 = 19p
• Путь 8: Рынок → Нижняя дорога (2p) → Средняя дорога (5p) → Центральная дорога (2p) → Нижняя дорога к замку (8p) = 2 + 5 + 2 + 8 = 17p
• Путь 9: Рынок → Нижняя дорога (2p) → Центральная дорога (2p) → Верхняя дорога к замку (10p) = 2 + 2 + 10 = 14p
• Путь 10: Рынок → Нижняя дорога (2p) → Центральная дорога (2p) → Нижняя дорога к замку (8p) = 2 + 2 + 8 = 12p
• Путь 11: Рынок → Нижняя дорога (2p) → Центральная дорога (2p) → еще одна центральная дорога (2p) → Верхняя дорога к замку (10p) = 2 + 2 + 2 + 10 = 16p
• Путь 12: Рынок → Нижняя дорога (2p) → Центральная дорога (2p) → еще одна центральная дорога (2p) → Нижняя дорога к замку (8p) = 2 + 2 + 2 + 8 = 14p
• Путь 13: Рынок → самая нижняя дорога (2p) → Центральная дорога (2p) → Верхняя дорога к замку (10p) = 2 + 2 + 10 = 14p
• Путь 14: Рынок → самая нижняя дорога (2p) → Центральная дорога (2p) → Нижняя дорога к замку (8p) = 2 + 2 + 8 = 12p
• Путь 15: Рынок → самая нижняя дорога (2p) → еще одна центральная дорога (5p) → Верхняя дорога к замку (10p) = 2 + 5 + 10 = 17p
• Путь 16: Рынок → самая нижняя дорога (2p) → еще одна центральная дорога (5p) → Нижняя дорога к замку (8p) = 2 + 5 + 8 = 15p
• Путь 17: Рынок → самая нижняя дорога (2p) → еще одна центральная дорога (5p) → еще одна центральная дорога (2p) → Верхняя дорога к замку (10p) = 2 + 5 + 2 + 10 = 19p
• Путь 18: Рынок → самая нижняя дорога (2p) → еще одна центральная дорога (5p) → еще одна центральная дорога (2p) → Нижняя дорога к замку (8p) = 2 + 5 + 2 + 8 = 17p
• Путь 19: Рынок → самая нижняя дорога (2p) → еще одна центральная дорога (2p) → Верхняя дорога к замку (10p) = 2 + 2 + 10 = 14p
• Путь 20: Рынок → самая нижняя дорога (2p) → еще одна центральная дорога (2p) → Нижняя дорога к замку (8p) = 2 + 2 + 8 = 12p
• Путь 21: Рынок → самая нижняя дорога (2p) → Центральная дорога (2p) → еще одна центральная дорога (2p) → Верхняя дорога к замку (10p) = 2 + 2 + 2 + 10 = 16p
• Путь 22: Рынок → самая нижняя дорога (2p) → Центральная дорога (2p) → еще одна центральная дорога (2p) → Нижняя дорога к замку (8p) = 2 + 2 + 2 + 8 = 14p

Чтобы найти кратчайший путь, можно использовать алгоритм Дейкстры, но для такой простой схемы можно перебрать пути вручную.

Рассмотрим пути, начинающиеся с самых дешевых дорог от рынка:

• Путь: Рынок → 2p → 2p (центральная) → 8p (к замку) = 2 + 2 + 8 = 12p.
• Путь: Рынок → 2p → 2p (центральная) → 2p (еще одна) → 8p (к замку) = 2 + 2 + 2 + 8 = 14p.
• Путь: Рынок → 2p → 5p → 2p (к замку) = 2 + 5 + 2 = 9p. (Ошибочно, не идет к замку)
• Путь: Рынок → 2p → 5p → 2p (центральная) → 8p (к замку) = 2 + 5 + 2 + 8 = 17p.
• Путь: Рынок → 2p → 5p → 2p (центральная) → 10p (к замку) = 2 + 5 + 2 + 10 = 19p.
• Путь: Рынок → 2p → 2p (центральная) → 10p (к замку) = 2 + 2 + 10 = 14p.
• Путь: Рынок → 2p → 2p (центральная) → 2p (еще одна) → 10p (к замку) = 2 + 2 + 2 + 10 = 16p.

Рассмотрим путь, проходящий через узел с ценой 2p, который ведет к замку с ценой 8p:

• Путь: Рынок (2p) → узел → узел (2p) → Замок (8p) = 2 + 2 + 8 = 12p.

Рассмотрим путь, проходящий через узел с ценой 2p, который ведет к замку с ценой 10p:

• Путь: Рынок (2p) → узел → узел (2p) → Замок (10p) = 2 + 2 + 10 = 14p.

Рассмотрим путь, проходящий через узел с ценой 2p, который ведет к другому узлу с ценой 2p, а затем к замку с ценой 8p:

• Путь: Рынок (2p) → узел (2p) → узел (2p) → Замок (8p) = 2 + 2 + 2 + 8 = 14p.

Рассмотрим путь, проходящий через узел с ценой 2p, затем 2p, затем 2p, и к замку с ценой 10p:

• Путь: Рынок (2p) → узел (2p) → узел (2p) → узел (2p) → Замок (10p) = 2 + 2 + 2 + 10 = 16p.

Кратчайший путь получается, если выбрать дорогу за 2p, затем дорогу за 2p, и затем дорогу за 8p.

• Путь: Рынок → 2p → 2p → 8p = 12p.

Проверим еще раз:

• Рынок → 2p → 2p → 8p (к замку) = 12p.
• Рынок → 2p → 2p → 2p → 8p (к замку) = 14p.
• Рынок → 2p → 5p → 2p → 8p (к замку) = 17p.
• Рынок → 4p → 2p → 8p (к замку) = 14p.
• Рынок → 4p → 2p → 10p (к замку) = 16p.
• Рынок → 12p → 8p (к замку) = 20p.
• Рынок → 12p → 10p (к замку) = 22p.

Самый дешевый путь: 2p + 2p + 8p = 12p.

Ответ: 12 рублей.