I found this interesting Graph question on CSES Flight Routes . The question basically describes a directed graph consisting of N Nodes and M edges. We need to start from the Node 1 (source) and reach Node N (destination). (Traversing the same nodes twice is also allowed). At the end , we need to calculate the cost of first K minimum paths from source to destination.
I approached this initially as a variation of Djisktra's algorithm where instead of just 1 shortest path , I calculated the K shortest paths for all possible Nodes. The solution has a time complexity of O(M*K log(N*K)*KlogK)
I tried improving onto the TC and instead of sorting every time , I used an array of Max Priority Queues , each of which has exactly K elements. This cut down the time complexity to O(M*K log(N*K)*logK)
I still got TLE in the last test case and not able to comprehend what more can be optimized.
Suppose a vertex v is connected to two vertices a and b. The weight of edge a->v is x and weight of edge b->v is y and x < y. The distance of vertices a and b from source are respectively dis[a] and dis[b] and dis[a] < dis[b]. Vertex v is not discovered yet and dis[v] = INF.
When we reach vertex v from vertex a, its distance is updated as dis[v] = min(dis[v],dis[a] + x) and v is pushed into the queue. Again when we reach v from b, its distance again is updated as dis[v] = min(dis[v],dis[b] + y) and v is pushed into the queue with this new distance. Now in the queue vertex v is present two times with two different distances, hence distance of all vertices connected to v will be checked two times. This may happen that a vertex is connected to a lot of vertices and cause unnecessary execution and give TLE. Instead use a set and whenever you insert a vertex into the set, if it was present there before erase that and then insert new one. Here is my submission-
(https://cses.fi/paste/eab46c0b3d84cffc17b8f6/)