i solved cses(graph) flight paths qn( https://cses.fi/problemset/task/1196 ), there is an explanation given in gfg(https://www.geeksforgeeks.org/1st-to-kth-shortest-path-lengths-from-node-1-to-n-in-given-graph/) i couldnt find out how they calculated the time complexity as O((n+m)klogk)) cuz i am getting a diff time complexity...can some one explain how did they come up with that time complexity.....thanks in advance..
Your URL broken, you put
)at the end of URLIn standard dijkstra's, we maintain the shortest route. In this problem, we'll only consider the k shortest path to reach each vertex. It could be save in 2-dimension array dist[n][k] where dist[i][j] is the j shortest path to reach vertex i. The initial state is dist[1][1] = 0. We can find the result by modifying dijkstra a little bit. My submission
i got the AC for the qn but the thing is how did the time complexity for the problem became O((n+m)klogk) as given in gfg i got a different result...what is the time complexity did you get
O((n + m)k * log(nk))