Можно считать,  что мы имеем ориентированный взвешенный граф,  у которого максимальная степень вершины равна трём .

Равна она трём потому,  что нам всегда выгодно ехать как можно дальше,  потому что мы заплатили за всю дистанцию.

То есть из какой-то станции ребра с весами C1,  C2 и C3 проводим в как можно более далёкие станции.

Тогда это получается очень сильно разреженный граф,  так как N<=1e4.

На этом графе запускаем алгоритм Дейкстры для разреженных графов.

Я использовал вариант за O(Nlog2N)  с std :: set.

Для расчёта того,  куда проводить ребра,  я использовал бинарный поиск.  И немного запорол реализацию этого поиска.

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

Это послужило причиной WA#6.

Причиной WA#2 послужило то,  что я забыл сделать обновление расстояния до пункта назначения.  Так как ребра идут жадно,  то пункт назначения проезжался и в очередь не попадал,  и расстояние соответственно никогда не обновлялось.