0/1 BFS | Competitive Programming

Basics:

(1)   https://cp-algorithms.com/graph/01_bfs.html.

(2)   http://shakilcompetitiveprogramming.blogspot.com/2016/05/01-bfs.html.

(3)   https://codeforces.com/blog/entry/22276.

(4)   https://www.dropbox.com/s/sgzwlmsmx5rrrug/0-1%20BFS.pdf?dl=0.

(5)   https://www.geeksforgeeks.org/0-1-bfs-shortest-path-binary-graph/.

(6)   https://gist.github.com/praval-singhal/d74ca19a041d888d4a2fe9c7615d985b#file-kaththi-cpp.

Problems:

(1)   Chef and Reversing (Codechef).

(2)   KATHTHI – KATHTHI (SPOJ).

(3)   Topcoder SRM-436 Div-1, 500 (Topcoder).

(4)   Vjudge: 1.

(5)   A2OJ.

/// 0_1-BFS.cpp

/// (Data Structure: graph, cost, visit, deque)

vector<int> g[100001],cost[100001];

int dist[100001]; /// initially= INT_MAX

bool vis[100001];

int bfs01(int s, int n)

{

    for(int i=0;i<n+1;i++)

    dist[i]=INT_MAX, vis[i]=0;

    deque<int>q;

    q.push_front(s);

    dist[s]=0;

    while(!q.empty())

    {

        int u= q.front();

        q.pop_front();

        if(vis[u]) continue;

        vis[u]=true;

        for(int i=0;i<g[u].size();i++)

        {

            int v=g[u][i];

            if(dist[u]+cost[u][i]<=dist[v])

            {

                dist[v]=dist[u]+cost[u][i];

                if(cost[u][i]==0)

                    q.push_front(v);

                else q.push_back(v);

            }

        }

    }

    return dist[n-1];

}