Alternate solution that I find pretty cool:
We want to find shortest paths with a variety of starting points. This brought to mind the multiple source shortest path problem, which is basically the same as single source, except you add all starting points to your queue/priority_queue with distance 0.
Now, this doesn’t work since your path will just go from like special->not_special->same_special which is not allowed since the start and end must be distinct.
The next idea is to only choose some of them as starting points. Then, if the optimal pair is (a,b), you need exactly one of (a,b) to be chosen as a starting point, and then you will find the answer as the shortest distance from a starting special point to a nonstarting special point.
How do we decide which to choose as starting points? Here’s a nice step - we win if we choose exactly one of the starting points. Notice if we choose a RANDOM set of starting points, there’s a 1/2 chance that we chose exactly one as a starting point. Now, if we iterate choosing a random set of starting points enough times, we will find the answer with high probability.
I chose MAGIC=20 (1/2^20 chance of failing a single test), here’s the implementation: CodeChef: Practical coding for everyone.
Complexity is O(nlogm) per iteration, and a bit of math can help choose a good number of iterations (or just until time runs out).