So I’m doing this problem, and I coded a simple Dijkstra’s that WAs on most of the test cases. It’s methodology was the do a Dijkstra’s, treating an edge as 0 cost if it was unique and its cost otherwise.
I know why this is wrong- changing an edge and moving along it can affect the other node as well. So I planned to have a node state with the current location, the previous color, and whether I changed the previous color and then do a Dijkstra’s. However, I’m not sure if this would pass under the time limt.
To calculate the big O of such a solution: if your node state is (current location, previous color), notice that each location only has O(degree) possible previous colors. Therefore you have only O(m) nodes, which seems fine. However, notice that each node has O(degree) outgoing edges, so in the worst case this is a graph with O(n^2) edges.
Then you have to optimize. Notice that it’s pointless to visit the same location with more than two different previous colors, since two different previous colors would cover all possible outgoing colors. Then if you visit each location only up to two times, the solution only visits O(m) edges, and is O(m logn) with Dijkstra’s, as desired.
There’s also some implementation details like how to represent the nodes. Might be easiest to use a map, which won’t be much slower since the solution is already O(mlogn).
Notice that it’s pointless to visit the same location with more than two different previous colors, since two different previous colors would cover all possible outgoing colors.
What do you mean by that two different previous colors would cover all of them?
One is less clever and does the algorithm that I suggested, having a state of (node, mode, input color) and visiting each node only up to twice: https://oj.uz/submission/379870 . This barely passes the time limit so maybe you should focus on the first solution.
Notice that it’s pointless to visit the same location with more than two different previous colors, since two different previous colors would cover all possible outgoing colors.
Could someone elaborate/justify this? My current understanding is that, after you pop (node, some color) out of the priority queue for two different “some color” then you can just ignore all other (node, some color) that are still in the priority queue. Maybe I’m misunderstanding something though.