You are not logged in. Please login at to post your questions!


Dijkstra's algorithm using STL set


void dijkstra(int v){ fill(d,d + n, inf); d[v] = 0; int u; set<pair<int,int> > s; s.insert({d[v], v}); while(!s.empty()){ u = s.begin() -> second; s.erase(s.begin()); for(auto p : adj[u]) //adj[v][i] = pair(vertex, weight) if(d[p.first] > d[u] + p.second){ s.erase({d[p.first], p.first}); d[p.first] = d[u] + p.second; s.insert({d[p.first], p.first}); } } }

I managed to implement Dijkstra's algorithm using heaps but it was extremely long, so I decided to try implementing using sets. However, in the above implementation (source: CF), I was unable to understand the part for(auto p: adj[u]) and the stuff in the loop. I haven't manipulated a set of pairs or priority queue of pairs before, I understand this is c++11 usage, but now how it works. Could someone please explain, and if possible, provide an equivalent non c++11 statement?

asked 01 Jan '16, 18:42

sandy999's gravatar image

accept rate: 10%

Answer is hidden as author is suspended. Click here to view.

answered 01 Jan '16, 21:05

sarvagya3943's gravatar image

accept rate: 36%

Thanks a lot :) This was damn useful, especially with INOI just a few days away

(02 Jan '16, 14:35) nishanthta4★

Glad to hear that! Just read the topcoder tutorial i mentioned and it will become crystal clear :D

(02 Jan '16, 14:48) sarvagya39434★

Thanks a ton @sarvagya3943 for taking the pain to explain it in such great detail! :D

(03 Jan '16, 20:24) sandy9992★
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text]( "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:


question asked: 01 Jan '16, 18:42

question was seen: 2,840 times

last updated: 03 Jan '16, 20:24