dijkstra's algorithm problems--getting tle
I m getting tle in only 2 test cases of this problem. here's my code link--
Auto comment: topic has been updated by typing_singh (previous revision, new revision, compare).
Your use of vis is not correct. if (!vis[v]&&dist[v] > dist[u] + weight)
if (!vis[v]&&dist[v] > dist[u] + weight)
Just remove it. It is enough to check if dist[v] can be relaxed. This is the case if a longer path is cheaper because sum of weights are less than a earlier, shorter path.
okay..but still giving tle. thanks for replying spookywooky
Sorry, I was wrong ;)
You need a vis array here. But not inside the loop over the children. You should check vis array just after pop() from the queue.
Since it is a priority_queue, the first time a node is popped from the queue the path is shortest, so all pops after the first one can be ignored.
Just write this line "if(dist[u]<w)continue;" before the for loop in shortestpath function, here "w=pq.top().first".
AC..thanks a lot man! can you explain about it little bit (if possible).i_am_legend1
You can read about it from here http://e-maxx.ru/algo/dijkstra_sparse.