My AC program gives same output.
Have you considered more than one edge from between 2 vertices?
I am not sure if the judge input has such case, but the problem statment doesn't avoid that.
My signature:
Please make discussion about the algorithm BRFORE posting source code.
We can learn much more in discussion than reading source code.
.. wrote:My AC program gives same output.
Have you considered more than one edge from between 2 vertices?
I am not sure if the judge input has such case, but the problem statment doesn't avoid that.
The judge input hasn't such case , becase I had checked it
I'm using a very naive algorithm: a simple BFS + priority queue (without checking if a node has been visited, always inserting in the queue). However, my algorithm doesn't seem to work. I was getting TLE, but now I'm getting WA. I realized that there can be zero-weighted cycles, which can cause my algo to infinite loop.
I could use some tips, inputs, or some reference to a classic kth shortest path algorithm.
Thank you for the test case. As I said in my previous post, a zero-sized loop could be even worse
4 4
1 4 10
1 2 0
2 3 0
3 1 0
1 4 10000
I tried some ideas like only inserting a node K times in the queue, but that didn't work. Could someone give some references to Kth shortest paths algorithms? I couldn't find anything really useful on the web. I would also appreciate some ideas on how to solve this problem (it's not like I want someones code, but just some ideas that could lead me to the right direction )
I did a simple and not too fast exhaustive search (dfs) keeping a top-k of distances from the source per node. The break-off condition for the search is when a distance outside the top-k is reached. At the end of the search the answer is in k-th place in the top-k of the target node.
A resonable speed-up (but not spectacular) was made by searching the nodes closest to the current node first (sorting the adjacency list). You can, off course, visit a node more than once during dfs.