I am struggled with this problem…
I read the editorial and seems like my submissions in contest matched what the editorial said.
I implemented Dijkstra and SPFA (that was the “Bellman-Ford + Queue” in the editorial) and submitted in practice session but getting TLE. I even submitted setter’s solution with no luck.
Why is the issue? Is it possible that setter’s solution is not guaranteed to finish the test cases within time limit?
Hi, it’s not strange at all setter’s solution is a clear version so everyone could get the idea to solve. You might see a very nice solution of the tester with lots of useful improvements. Let it challenge you
I could understand if the author’s solution is NOT an intended solution. Judging from the sketch of author’s solution idea I think this is exactly what we want, without any optimization mentioned.
I don’t think challenge includes optimizing certain constant time operations so as to pass the time limit. Moreover in other contests it is known that the time limit is certain multiple of how fast the slowest intended solution could pass the test data (I even heard that the factor was 10 in ACM ICPC World Final).
It would be discouraging to spent over days to get a suggested solution worked due to tight time limit.