# HackerEarth Black and White problem solution

In this HackerEarth Black and White problem solution, You are given a graph G consisting of N nodes and M edges. Each node of G is either colored in black or white. Also, each edge has a particular weight. Now, you need to find the least expensive path between node 1 and node N, such that the difference of the number of black nodes and white nodes on the path is no more than.

It is guaranteed G does not consist of multiple edges and self-loops.

## HackerEarth Black and White problem solution.

`#include<bits/stdc++.h>using namespace std;#define pb push_back#define mp make_pair#define X first#define Y second#define zero 1001   #define black 0#define white 1#define ini(a) memset(a,-1,sizeof(a))vector<pair<int,int> > g[1005];int control[1005];int dp[1005][2005];int dijkstra(int source,int n){    ini(dp);    set<pair<int,pair<int,int> > > s;    int index=(control[source]==black)?(zero-1):(zero+1);     dp[source][index]=0;    s.insert(mp(0,mp(source,index)));     while(!s.empty()){        int u=s.begin()->Y.X;        int dif=s.begin()->Y.Y;        s.erase(s.begin());        for(int i=0;i<g[u].size();i++){            int v=g[u][i].X;            int w=g[u][i].Y;            int ind=(control[v]==black)?(dif-1):(dif+1);            if(dp[v][ind]==-1||dp[v][ind]>dp[u][dif]+w){                    s.erase(mp(dp[v][ind],mp(v,ind)));                    dp[v][ind]=dp[u][dif]+w;                    s.insert(mp(dp[v][ind],mp(v,ind)));            }        }    }    int ans=INT_MAX;    for(int i=-1;i<=1;i++){        if(dp[n][zero+i]!=-1)            ans=min(ans,dp[n][zero+i]);    }    return ans;}int main(){    int n,m;    scanf("%d%d",&n,&m);    for(int i=0;i<m;i++){        int u,v,l;        scanf("%d%d%d",&u,&v,&l);        g[u].pb(mp(v,l));    }    for(int i=1;i<=n;i++){        scanf("%d",&control[i]);    }    int ans=dijkstra(1,n);    if(ans==INT_MAX)        ans=-1;    printf("%d\n",ans);}`

### Second solution

`import java.io.OutputStream;import java.io.IOException;import java.io.InputStream;import java.io.PrintWriter;import java.util.Arrays;import java.io.BufferedInputStream;import java.util.PriorityQueue;import java.util.ArrayList;import java.util.AbstractCollection;import java.io.FilterInputStream;import java.io.InputStream;public class Main {    public static void main(String[] args) {        new Thread(null, new Runnable() {            public void run() {                new Main().solve();            }        }, "1", 1 << 26).start();    }    void solve() {        InputStream inputStream = System.in;        OutputStream outputStream = System.out;        ScanReader in = new ScanReader(inputStream);        PrintWriter out = new PrintWriter(outputStream);        BlackandWhite solver = new BlackandWhite();        solver.solve(1, in, out);        out.close();    }    static class BlackandWhite {        ArrayList<pair>[] arrayLists;        int[][] dp;        int[] type;        int ze = 1005;        private int dfs(int start, int n) {            PriorityQueue<pair> priorityQueue = new PriorityQueue<>();            priorityQueue.add(new pair(start, 0, type[start] == 0 ? ze - 1 : ze + 1));            while (!priorityQueue.isEmpty()) {                pair tt = priorityQueue.poll();                if (dp[tt.node][tt.diff] != 1000000000) continue;                dp[tt.node][tt.diff] = tt.weight;                for (int i = 0; i < arrayLists[tt.node].size(); i++) {                    if (dp[arrayLists[tt.node].get(i).node][(type[arrayLists[tt.node].get(i).node] == 0 ? tt.diff - 1 : tt.diff + 1)] == 1000000000) {                        priorityQueue.add(new pair(arrayLists[tt.node].get(i).node, tt.weight + arrayLists[tt.node].get(i).weight, (type[arrayLists[tt.node].get(i).node] == 0 ? tt.diff - 1 : tt.diff + 1)));                    }                }            }            return Math.min(dp[n][ze], Math.min(dp[n][ze - 1], dp[n][ze + 1]));        }        public void solve(int testNumber, ScanReader in, PrintWriter out) {            int n = in.scanInt();            int m = in.scanInt();            if (n < 1 || n > 1000) throw new RuntimeException();            if (m < 1 || m > 10000) throw new RuntimeException();            arrayLists = new ArrayList[n + 1];            dp = new int[n + 1][2 * (1005)];            for (int i = 0; i <= n; i++) Arrays.fill(dp[i], 1000000000);            for (int i = 0; i <= n; i++) arrayLists[i] = new ArrayList<>();            for (int i = 0; i < m; i++) {                int u = in.scanInt();                int v = in.scanInt();                int l = in.scanInt();                if (l < 1 || l > 1000) throw new RuntimeException();                arrayLists[u].add(new pair(v, l));            }            type = new int[n + 1];            for (int i = 1; i <= n; i++) type[i] = in.scanInt();            int ans = dfs(1, n);            if (ans == 1000000000) out.println(-1);            else out.println(ans);        }        class pair implements Comparable<pair> {            int node;            int weight;            int diff;            public int compareTo(pair o) {                return this.weight - o.weight;            }            public pair(int node, int weight, int diff) {                this.node = node;                this.weight = weight;                this.diff = diff;            }            public pair(int node, int weight) {                this.node = node;                this.weight = weight;            }        }    }    static class ScanReader {        private byte[] buf = new byte[4 * 1024];        private int index;        private BufferedInputStream in;        private int total;        public ScanReader(InputStream inputStream) {            in = new BufferedInputStream(inputStream);        }        private int scan() {            if (index >= total) {                index = 0;                try {                    total = in.read(buf);                } catch (Exception e) {                    e.printStackTrace();                }                if (total <= 0) return -1;            }            return buf[index++];        }        public int scanInt() {            int integer = 0;            int n = scan();            while (isWhiteSpace(n)) n = scan();            int neg = 1;            if (n == '-') {                neg = -1;                n = scan();            }            while (!isWhiteSpace(n)) {                if (n >= '0' && n <= '9') {                    integer *= 10;                    integer += n - '0';                    n = scan();                }            }            return neg * integer;        }        private boolean isWhiteSpace(int n) {            if (n == ' ' || n == '\n' || n == '\r' || n == '\t' || n == -1) return true;            else return false;        }    }}`