0-1 BFS
O(n + m)Shortest paths when every edge weighs 0 or 1, using a deque instead of a priority queue: 0-edges go to the front, 1-edges to the back. Linear time, so it beats Dijkstra whenever it applies. Common in grid problems where some moves are free.
// use it on
Codeforces 1063B: Labyrinth ↗
Grid walk where up/down moves are free and left/right moves are limited. Model the limited moves as weight-1 edges and 0-1 BFS gives the minimum consumption.
// the code
// adj[u] = {{v, w}, ...} with w in {0, 1}
vector<int> zero_one_bfs(int src, vector<vector<pair<int, int>>>& adj) {
int n = adj.size();
vector<int> dist(n, INT_MAX);
deque<int> dq;
dist[src] = 0;
dq.push_back(src);
while (!dq.empty()) {
int u = dq.front();
dq.pop_front();
for (auto [v, w] : adj[u])
if (dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
if (w == 0) dq.push_front(v);
else dq.push_back(v);
}
}
return dist;
}// more shortest paths