Commit96d4b88

and

authored

Update src/graph/01_bfs.md

Co-authored-by: Oleksandr Kulkov <adamant.pwn@gmail.com>

1 parent6e98192 commit96d4b88Copy full SHA for 96d4b88

File tree

+10

-14

lines changed

+10

-14

lines changed

Lines changed: 10 additions & 14 deletions

Original file line number	Diff line number	Diff line change
@@ -21,20 +21,16 @@ The general form of Dijkstra's algorithm is (here a `set` is used for the priori
`21`	`21`	```cpp
`22`	`22`	`d.assign(n, INF);`
`23`	`23`	`d[s] = 0;`
`24`		`- set<pair<int, int>> q;`
`25`		`- q.insert({0, s});`
`26`		`- while (!q.empty()) {`
`27`		`- int v = q.begin()->second;`
`28`		`- q.erase(q.begin());`
`29`		`-`
`30`		`- for (auto edge : adj[v]) {`
`31`		`- int u = edge.first;`
`32`		`- int w = edge.second;`
`33`		`-`
`34`		`- if (d[v] + w < d[u]) {`
`35`		`- q.erase({d[u], u});`
`36`		`- d[u] = d[v] + w;`
`37`		`- q.insert({d[u], u});`
	`24`	`+ priority_queue<pair<int, int>> q = {{0, s}};`
	`25`	`+ while (!empty(q)) {`
	`26`	`+ int[dv, v] = q.top();`
	`27`	`+ q.pop();`
	`28`	`+ if (-dv == d[v]) {`
	`29`	`+ for (auto[u, w] : adj[v]) {`
	`30`	`+ if (d[v] + w < d[u]) {`
	`31`	`+ d[u] = d[v] + w;`
	`32`	`+ q.insert({-d[u], u});`
	`33`	`+ }`
`38`	`34`	`}`
`39`	`35`	`}`
`40`	`36`	`}`

Comments

(0)