We can develop the algorithm by closely studying Dijkstra's algorithm and thinking about the consequences that our special graph implies.

The general form of Dijkstra's algorithm is (here a`set` is used for the priority queue):

d.assign(n, INF);

d[s] =0;

set<pair<int,int>> q;

q.insert({0, s});

while (!q.empty()) {

int v = q.begin()->second;

q.erase(q.begin());

=== "C++"

```cpp

d.assign(n, INF);

d[s] = 0;

set<pair<int, int>> q;

q.insert({0, s});

while (!q.empty()) {

int v = q.begin()->second;

q.erase(q.begin());

}

=== "Python"

```py

from heapq import heappop, heappush

We can notice that the difference between the distances between the source`s` and two other vertices in the queue differs by at most one.

Especially, we know that $d[v] \le d[u] \le d[v] + 1$ for each $u \in Q$.

We can simply use a normal queue, and append new vertices at the beginning if the corresponding edge has weight $0$, i.e. if $d[u] = d[v]$, or at the end if the edge has weight $1$, i.e. if $d[u] = d[v] + 1$.

This way the queue still remains sorted at all time.

vector<int>d(n, INF);

d[s] = 0;

deque<int> q;

q.push_front(s);

while (!q.empty()) {

int v = q.front();

q.pop_front();

for (auto edge : adj[v]) {

int u = edge.first;

int w = edge.second;

if (d[v] + w < d[u]) {

d[u] = d[v] + w;

if (w == 1)

q.push_back(u);

else

q.push_front(u);

=== "C++"

```cpp

vector<int> d(n, INF);

d[s] = 0;

deque<int> q;

q.push_front(s);

while (!q.empty()) {

int v = q.front();

q.pop_front();

for (auto edge : adj[v]) {

int u = edge.first;

int w = edge.second;

if (d[v] + w < d[u]) {

d[u] = d[v] + w;

if (w == 1)

q.push_back(u);

else

q.push_front(u);

}

}

}

}

```

=== "Python"

```py

d =[float("inf")] * n

d[s] = 0

q = deque([s])

while q:

v = q.popleft()

for u, w in adj[v]:

if d[v] + w < d[u]:

d[u] = d[v] + w

if w == 1:

q.append(u)

else:

q.appendleft(u)

```