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;
}
}
}
0 Comments