Путь A-B-C-E имеет длину 15, попробуем убедиться, что путей короче не бывает (если вы думаете, что это очевидно, то вы почти наверняка забыли рассмотреть пути вида A-B-E-C-A-D-E, путей с многократными заходами в пункты тут много).
- Пусть C-E (длина 10) есть в маршруте. Тогда для более короткого маршрута длина остальных отрезков пути должна быть не больше 4, но наименьшие длины других отрезков 2 и 3, либо A-D длины 4. Не подходит, C-E отбрасываем - по нему путь короче 15 не проходит.
- Аналогично с A-C (длина 9): на оставшийся путь остается не больше 5. Но из C в E не попасть на 5, так как все отрезки, идущие в E, имеют длину не меньше 5, а тот, который имеет длину 5, начинается в B.
После отбрасывания остаются только 2 пути A-B-C-D-E и A-D-C-B-E, но эти пути длиннее 15.
15
Объяснение:
Изобразим схему дорог на рисунке.
Путь A-B-C-E имеет длину 15, попробуем убедиться, что путей короче не бывает (если вы думаете, что это очевидно, то вы почти наверняка забыли рассмотреть пути вида A-B-E-C-A-D-E, путей с многократными заходами в пункты тут много).
- Пусть C-E (длина 10) есть в маршруте. Тогда для более короткого маршрута длина остальных отрезков пути должна быть не больше 4, но наименьшие длины других отрезков 2 и 3, либо A-D длины 4. Не подходит, C-E отбрасываем - по нему путь короче 15 не проходит.
- Аналогично с A-C (длина 9): на оставшийся путь остается не больше 5. Но из C в E не попасть на 5, так как все отрезки, идущие в E, имеют длину не меньше 5, а тот, который имеет длину 5, начинается в B.
После отбрасывания остаются только 2 пути A-B-C-D-E и A-D-C-B-E, но эти пути длиннее 15.