On the flipside I went with Dijkstra straight away, but it took me a considerable amount of time to realize that it cannot be applied as-is. The reason is that the relaxation rule (dist[u] + length(u, v) < dist[v]) breaks because going along the “longer” edge (that is, switching gear) may pay off better in the long run. To solve that, one needs to do a “3D” version of the algorithm, that is, keep the minimum (tentative) distance for each combination of location and gear.

Once I got that down and the example worked, the key thing was to use priority queue in the implementation. Since there is none in the standard lib, I used a plain MapSet+Enum.min_by with the tip from Wikipedia:

Instead of filling the priority queue with all nodes in the initialization phase, it is also possible to initialize it to contain only source ; then, inside the if alt < dist[ v ] block, the node must be inserted if not already in the queue (instead of performing a decrease_priority operation)

With that, I arrived at the solution after a couple of seconds even if I enlarged the cave by plain experimentation so that I could find the globally shortest path.