×

Dijkstra's algorithm using STL set

 0 1 void dijkstra(int v){ fill(d,d + n, inf); d[v] = 0; int u; set > 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 2★sandy999 391●1●16●38 accept rate: 10%

 3 Answer is hidden as author is suspended. Click here to view. answered 01 Jan '16, 21:05 (suspended) accept rate: 36% Thanks a lot :) This was damn useful, especially with INOI just a few days away (02 Jan '16, 14:35) 2 Glad to hear that! Just read the topcoder tutorial i mentioned and it will become crystal clear :D (02 Jan '16, 14:48) Thanks a ton @sarvagya3943 for taking the pain to explain it in such great detail! :D (03 Jan '16, 20:24) sandy9992★
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• 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:

×278
×165
×160

question asked: 01 Jan '16, 18:42

question was seen: 2,840 times

last updated: 03 Jan '16, 20:24