kth path- cf 1196F

Here's a second solution. I haven't submitted this one myself, so please feel free to comment if you spot any errors. (Although I received this solution from Dorijan, I wrote it up myself, so all blame for any errors should go to me.)

Eliminate all edges except the K cheapest ones, with ties broken arbitrarily. Then, run N Dijkstra's iterations or an efficient all-pairs shortest paths algorithm to find all possible lengths of paths. From here, sort the paths and pick the K'th least expensive one. This is correct because none of the paths we're looking for will include an edge other than one of the K cheapest ones. Moreover, it's fairly easy to see that this will run in time: there will be, at most, O(K2) paths resulting from this process.

Let X be the maximum length among the K cheapest edges. Any other edge must have length at least X, so any path containing another edge must have length at least X. Meanwhile, we can construct at least K paths with length at most X (simply take the K paths corresponding to the K edges), including all paths with length less than X, so the answer can be found among these paths