← All solutions

This problem can be solved using Dijkstra’s algorithm. The graph in which we’re interested has as vertices fourtuples (r, c, α, d), where

• (r, c) is a position in the city, indicating our position
• α is one of the four possible directions, indicating in which direction we are currently heading
• d is a boolean, indicating whether the cost of the last traversed street was doubled or not (so that we know whether or not to add its cost when turning or stopping)