how to solve this graph problem?
I have an idea, but at the moment it is \mathcal{O}(n^2) which is too slow.
I still have to ponder how to speed it up.
My Core Idea
I visualize the space in 2D. on the x-axis the index i and on the y-axis p_i. From a point we can only travel to the top-right and bottom-left quadrants with respect to that point. For each point we precalculate the top-most, left-most, bottom-most and right-most points reachable (doable in \mathcal{O}(n)). I propose that the shortest path from u to v travels only trough these edges. I think this is the key to making a fast algorithm.
anyone got it yet ?
check 15th slide.