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?
There are two main approaches for this problem.
One is more clever and augments the graph with nodes of various possible colors: https://oj.uz/submission/377981
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.