В Хогвартсе есть 6 комнат, в которых живут соответственно Гарри, Рон, Драко, Невилл, Фред и Джордж. Гарри Поттеру срочно нужно добраться до Драко Малфоя, и сделать это как можно…
В Хогвартсе есть 6 комнат, в которых живут соответственно Гарри, Рон, Драко, Невилл, Фред и Джордж. Гарри Поттеру срочно нужно добраться до Драко Малфоя, и сделать это как можно быстрее, при этом Гарри знает, что комнаты Хогвартса соединены следующим образом: Расстояние между комнатами Гарри и Рона можно пройти за 3 минуты Расстояние между комнатами Рона и Невилла можно пройти за 7 минут, между Роном и Джорджем тоже за 7 и между Роном и Фредом – за 4 Расстояние между Фредом и Джорджем можно пройти за 2 минуты Расстояние между Джорджем и Невиллом – за 5 минут, а между Джорджем и Драко – за 3 минуты Других путей в замке нет За какое кратчайшее время Гарри сможет добраться до Драко?
Краткий ответ: Гарри достигнет Драко за 12 минут.
Пошаговое решение
- Представим ситуацию как граф
- Узлы (комнаты): Гарри (Г), Рон (Р), Невилл (Н), Фред (Ф), Джордж (Дж), Драко (Др).
- Ребра с весами (время в минутах):
- Г — Р: 3
- Р — Н: 7
- Р — Дж: 7
- Р — Ф: 4
- Ф — Дж: 2
- Дж — Н: 5
- Дж — Др: 3
- Г и Др напрямую не связаны.
- Ключевая особенность
- Единственная связь к Драко — через Джорджa: путь к Драко должен оканчиваться Джордж → Драко (3 минуты).
- Вывод времени через Джорджa
- Значит общая минимальная длительность = минимальное время от Гарри до Джорджа + 3 минуты (на Джордж → Драко).
- Найдём минимальное время от Гарри до Джорджа.
- Рассмотрим пути Гарри → Джордж
- Г → Р → Джордж: 3 + 7 = 10 минут
- Г → Р → Фред → Джордж: 3 + 4 + 2 = 9 минут
- Г → Р → Невилл → Джордж: 3 + 7 + 5 = 15 минут
Наименьшее время до Джорджа — 9 минут через маршрут Г → Р → Фред → Джордж.
- Итог
- Время Г → Джордж = 9 минут.
- Добавляем 3 минуты на Джордж → Драко.
- Всего: 9 + 3 = 12 минут.
Итого, самый быстрый путь: Гарри → Рон → Фред → Джордж → Драко, суммарно 12 минут.
