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

×

Dijkstra's algorithm using STL set

0
1

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

2★sandy999
39111638
accept rate: 10%


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

answered 01 Jan '16, 21:05

sarvagya3943's gravatar image

4★sarvagya3943
(suspended)
accept rate: 36%

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

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

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
Preview

Follow this question

By Email:

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

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "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:

×278
×165
×160

question asked: 01 Jan '16, 18:42

question was seen: 2,840 times

last updated: 03 Jan '16, 20:24