I tried to solve the Hypertubes problem on Spoj but I am getting TLE.
I tried to store the graph in the adjacency list(using set) and then iterated over 0 to n and for every entry in its adjacency element, updated its distance. It gives WA on the 25th test case which I understand why it is giving WA. Also, I think its complexity is m*k*k*log(min(n,k*k)). log factor is coming from insertion in the set.
NOTE: Graph storing part is not giving TLE.
I had to store the graph as same as above(it will not give me TLE). I tried to use Disjoint set union for answering -1 if (n-1) index is not reachable from 0. If it is reachable then I tried to use priority_queue(Dijkstra) for finding the minimum distance from 0 to n-1 but it is giving me TLE on the 25th test case. I think that this approach has to be worked fine but it is throwing TLE. I also tried only Dijkstra without Disjoint set union but it still gives me TLE.
Here is my code which is getting TLE
My Questions are:
Can I get rid of this TLE?
Also, can someone mention what is expected complexity of this problem?
Is there any other methods to solve this question?
Edit 1: Here is proof that WA coming on 25th.