Указание:
Постройте граф населённых пунктов.
Решение:
Построим граф, вершинами которого будут населённые пункты, а рёбрами — дороги между ними.
По условию, путь состоит из двух частей: из в и из и . Найдём кратчайшие пути для этих частей. 1) Из в . Путь длиной является кратчайшим, поскольку все прочие пути проходят через рёбра длиной не меньше . 2) Из в . В вершину можно попасть через рёбра или . В первом случае кратчайший путь из в это длиной , а весь путь будет длины . Во втором случае само ребро (длины ) уже длиннее пути , значит, любой путь через будет длиннее . Итого мы получили кратчайшие пути для двух частей: и . Их объединение даёт искомый ответ. Кратчайший путь из в , проходящий через это длиной .