Brainless_Loco's blog

CSES Problem Set "Shortest Routes I" using Dijkstra algo
By Brainless_Loco, history, 4 years ago, In English

I was trying to solve Shortest Routes I problem using Dijkstra Algorithm. But I am getting TLE Verdict on 2 test cases and the rests were accepted. My Solution Link. I saw some solutions on online but i didn't understand those. Can anyone please let me know the problem with my code,how can i modify this code to get accepted?

Thanks in advance.

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (3)
| Write comment?
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it 
...
while(!q.empty()){
        ll x=q.top().F,y=q.top().S; ///x is negative cost for yth node
        q.pop();
        for(auto i:v[y]){
...

You should add if (-x > lev[y]) continue; after q.pop(); because you may push sub-optimal states into the priority queue before. You need to skip those states to avoid looping the neighbors of those nodes.

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

In the Dijkstra's algorithm, initially the distance to the starting node is 0 and the distance to all other nodes is infinite.

You need fill the array lev with INF, create a new array processed to know if a node has been processed or not. The new code would be like the following:

Code

You can also see my code in the following link: My code

→ Reply