Https://www.hackerrank.com/challenges/dijkstrashortreach/problem

#1

This problem is giving tle error for DIJkstras …so How can I optimise Algorithm

#2

Hey @anuranjan8319918906
In this problem, for a given graph with vertices, undirected edges with integer weights between them, and special vertex , the goal is to find the length of the shortest paths from to each of all vertices.

If all edges of have non-negative weights, the most well-known and also widely used method of solving this problem is to use Dijkstra’s algorithm implemented with a priority queue. In that case, the total time complexity of the algorithm is . This is true because each edge of the graph is examined exactly once, and such an examination can cause a constant number of updates in a priority queue containing either or vertices depending on the implementation. However, since each such operation on a priority queue has complexity proportional to the logarithm of its size, it does not matter if the queue contains or entries, since because is at most in this problem.

One important thing to note is that the last test file is specially designed to prevent inefficient solutions forgetting to delete already processed vertices from the priority queue. It targets solutions using a priority queue allowing multiple occurrences of the same vertex to be present in the queue.

Here refer to this solution : https://ide.codingblocks.com/s/353100

#3

you mean…using visited array we can use prirority queue

#4

Basically you have to code Disjkstra which is implemented using priority queue
I also sent u the code for reference if u don’t know how to implement using Priorty queue.

#5

https://ide.codingblocks.com/s/353123 …This Is my code using Priority Queue Almost same as urs…please tell why its showing TLE on one of the case

#6

Hey @anuranjan8319918906
Use

vector<pair<int, int>> gr[3001];

instead of map<list> …

#7

Hey @anuranjan8319918906
If u dont have any other doubt in this then please mark it as resolved :slight_smile:

#8

hello @anuranjan8319918906
u have reopened ur doubt, what issue u r facing now?

#9

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.