Научимся для начала решать задачу доехать за минимальную стоимость из одного перекрестка до другого. Для этого заведем m·4 вершин. Вершина — конец ребра на котором стоит колесница и направление, в котором она смотрит (по направлению на вторую вершину ребра, или в противоположном направлении). Проведем ребра между состояниями, между которыми можно перейти. А именно, из состояния, соответствующего колеснице, стоящей в начале ребра и смотрящей на другую вершину ребра, проведем ребро стоимости длинна ребра умноженная на коэффициент в состояние, в котором колесница стоит на второй вершине ребра и смотрит в ту же сторону. Так же, для каждой вершины отсортируем состояния, стоящие на этой вершине, по углу направления и проведем между соседними в таком порядке состояниями ребра стоимости угол между направлениями умноженный на коэффициент. Теперь запустим алгоритм Дейкстры из состояний, стоящих на начальной вершины, а за ответ возьмем минимальное из расстояний до состояний, стоящих на финальной вершине.

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

Обратите внимание, что если решение явно строит граф размера m·4·k, оно может не уложится в ограничения по памяти. Количество вершин на слое можно соптимизировать до m·2, а так же можно хранить расстояние только внутри последних двух слоев. Потому что никакое ребро не ведет из более позднего слоя в более ранний.