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("%dn",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;
        }

    }
}

coding problems solutions