I found this problem the most interesting out of all the problems. Here is the link to the contest: http://codeforces.com/gym/100286/. It’s problem D.
I tried to solve it using djkstra. I was trying to create a DAG, by always going forward ( increasing x ) until I hit a rectangle. After that I had 3 options, go through the rectangle, go up till the top of the rectangle and go down to the bottom. Then, I found a test case for which it didn’t work.
Later I figured, in the optimal path, all my horizontal paths will have y coordinates parallel to the rectangles bottom or top and all my vertical paths will have x coordinates parallel to the sides. With 1000 rectangles, I can have 2000 unique y-levels and 2000 unique x-levels. Therefore I can divide the whole grid into a 2000 by 2000 grid. Then run djkstra through it. The difficulty with this idea is to determine if the path is inside a rectangle, outside or on the boundary.
That’s all the idea I got. Didn’t find anything over the net either.