Блог пользователя Brainless_Loco

Автор Brainless_Loco, история, 4 года назад, По-английски

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.

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
...
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.

»
4 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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