HackerRank Minimum Penalty Path Solution

In this post, we will solve HackerRank Minimum Penalty Path Problem Solution.

Consider an undirected graph containing N nodes and M edges. Each edge M; has an integer cost, C, associated with it.
The penalty of a path is the bitwise OR of every edge cost in the path between a pair of nodes, A and B. In other words, if a path contains edges M1, M2,…, M, then the penalty for this path is C₁ OR C2 OR… OR Ck
Given a graph and two nodes, A and B, find the path between A and B having the minimal possible penalty and print its penalty; if no such path exists, print -1 to indicate that there is no path from A to B.
Note: Loops and multiple edges are allowed. The bitwise OR operation is known as or in Pascal and as | in C++ and Java.
Input Format
The first line contains two space-separated integers, N (the number of nodes) and M (the number of edges), respectively.

Each line of the M subsequent lines contains three space-separated integers U₁, Vi, and C₁, respectively, describing edge Mi connecting the nodes Ui and Vi and its associated penalty (Ci).
The last line contains two space-separated integers, A (the starting node) and B (the ending node), respectively

Output Format
Print the minimal penalty for the optimal path from node A to node B; if no path exists from node A to node B, print -1.

ample Input

Sample Output

Explanation
The optimal path is 1 →2→ 3.
C(1,2) = 1 and C(2,3) = 3.
The penalty for this path is: 1 OR 3 = 3, so we print 3.

HackerRank Minimum Penalty Path Problem Solution

Table of Contents

Minimum Penalty Path C Solution

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>

struct Node
{int data;
 int cost;
 struct Node *next;    
};

struct Node *x[1001]={NULL},*y[1001];

void insert(int a,int b,int cost){
    struct Node *node=(struct Node *)malloc(sizeof(struct Node));
    node->next=NULL;
    node->data=b;
    node->cost=cost;
    if(x[a]==NULL){
        x[a]=node;
        y[a]=node;
    }
    else
    {y[a]->next=node;
      y[a]=node;  
    }    
}

int ans=99999999;
static int dp[1001][1111];

void aa(int start){
 static int a[10000001],b[10000001],i,j,k,l;
 int start1=1,end1=1;

 struct Node *node;   
 a[1]=start;
 b[1]=0;
    
 while(start1<=end1){
     i=a[start1];
     j=b[start1];
     start1++;
     node=x[i];
     while(node!=NULL){
         if(dp[node->data][j|node->cost]==0){
             end1++;
             dp[node->data][j|node->cost]=1;
             a[end1]=node->data;
             b[end1]=j|node->cost;
         }
     node=node->next;
     }
 }   
}

int main() {
    int m,n,i,j,k,l,start,end;
    scanf("%d %d",&n,&m);
    
    for(i=1;i<=m;i++){
        scanf("%d %d %d",&k,&l,&j);
        insert(k,l,j);
        insert(l,k,j);
    }
    scanf("%d %d",&start,&end);
   
    aa(start);
    
    for(i=0;i<1111;i++){
        if(dp[end][i]){
            printf("%d",i);
            break;
        }
    }
    if(i==1111)
        printf("-1");
    return 0;
}

Minimum Penalty Path C++ Solution

#include<bits/stdc++.h>
using namespace std;
typedef long long int lli;
int vis[10000];
list<pair<int,int > > li[1000000];
int n,m,a,b;
int dp[1111+1][1029];
int is_cov[100000];
int ans=10000;
int dfs(int start,int val)
 {
  // cout<<start<<" "<<val<<endl;
    if(dp[start][val]!=-1) {
      vis[start]=0;
    return 0;}
    else if(start==b)
     {
       ans=min(ans,val);
       vis[start]=0;
    return 0;
  }
       
        dp[start][val]=1;
      list<pair<int,int> > :: iterator it;
      for(it=li[start].begin();it!=li[start].end();it++)
       {
   //      cout<<" dd "<<it->first<<endl;
          if(!vis[it->first])
           {
             vis[it->first]=1;
            
              dfs(it->first,it->second | val);
      }
       
    }
  //  cout<<"set "<<start<<" off "<<endl;
    vis[start]=0;
    return 0;
    }
  

 int main()
  {
    
     cin>>n>>m;
     memset(dp,-1,sizeof dp);
     
     for(int i=0;i<m;i++)
      {
        int x,y,v;
        scanf("%d %d %d",&x,&y,&v);
         li[x].push_back(make_pair(y,v));
         li[y].push_back(make_pair(x,v));
     }
  scanf("%d %d",&a,&b);
  
   vis[a]=1;
   dfs(a,0);
   if(ans==10000)
   cout<<-1<<endl;
   else
    printf("%d",ans);
    return 0;
  }

Minimum Penalty Path C Sharp Solution

using System.CodeDom.Compiler;
using System.Collections.Generic;
using System.Collections;
using System.ComponentModel;
using System.Diagnostics.CodeAnalysis;
using System.Globalization;
using System.IO;
using System.Linq;
using System.Reflection;
using System.Runtime.Serialization;
using System.Text.RegularExpressions;
using System.Text;
using System;

class Solution
{
    struct Road
    {
        public int to;
        public int cost;
    }
    class Node
    {
        public List<Road> roads;      
        public HashSet<int> results;
        public bool onQ;

        public Node()
        {
            results = new HashSet<int>();
            roads = new List<Road>();
        }
    }
       
    
    static int beautifulPath(int n, int[][] edges, int A, int B)
    {
        var nodes = new Node[n + 1];

        for (int i = 0; i < n+1; i++)
        {
            nodes[i] = new Node();
        }

        foreach(var edge in edges)
        {
            if (edge[0] != edge[1])
            {
                nodes[edge[0]].roads.Add(new Road() { to = edge[1], cost = edge[2] });
                nodes[edge[1]].roads.Add(new Road() { to = edge[0], cost = edge[2] });
            }
        }

        Queue<int> s = new Queue<int>();
        nodes[A].results.Add(0);
        nodes[A].onQ = true;
        s.Enqueue(A);

        while(s.Any())
        {
            int nIndex = s.Dequeue();
            var node = nodes[nIndex];
            node.onQ = false;

            foreach (Road road in node.roads)
            {               
                var nextnode = nodes[road.to];

                bool addedNew = false;
                foreach(var result in node.results)
                {
                    int nextR = result | road.cost;

                    if (!nextnode.results.Contains(nextR))
                    {
                        nextnode.results.Add(nextR);
                        addedNew = true;
                    }
                }

                if ((addedNew) && (nextnode.onQ == false))
                {
                    s.Enqueue(road.to);
                    nextnode.onQ = true;
                }
                            
            }
        }


        if(nodes[B].results.Any())
        {
            return nodes[B].results.Min();
        }
        return -1;
    }

    static void Main(string[] args)
    {
        TextWriter textWriter = new StreamWriter(@System.Environment.GetEnvironmentVariable("OUTPUT_PATH"), true);

        string[] nm = Console.ReadLine().Split(' ');

        int n = Convert.ToInt32(nm[0]);

        int m = Convert.ToInt32(nm[1]);

        int[][] edges = new int[m][];

        for (int i = 0; i < m; i++)
        {
            edges[i] = Array.ConvertAll(Console.ReadLine().Split(' '), edgesTemp => Convert.ToInt32(edgesTemp));
        }

        string[] AB = Console.ReadLine().Split(' ');

        int A = Convert.ToInt32(AB[0]);

        int B = Convert.ToInt32(AB[1]);

        int result = beautifulPath(n, edges, A, B);

        textWriter.WriteLine(result);

        textWriter.Flush();
        textWriter.Close();
    }
}

Minimum Penalty Path Java Solution

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {

    static int beautifulPath(int[][] edges, int A, int B) {
        Map<Integer, Set<Edge>> adjacents = makeAdjacencyList(edges);
        
        boolean[][] dp = new boolean[1001][1024];
        
        dfs(A, 0, adjacents, dp);
        
        for(int i=0; i<1024; ++i) {
            if(dp[B][i]) return i;
        } 
        
        return -1;
    }
    
    private static void dfs(int from, int cost, Map<Integer, Set<Edge>> adjacents, boolean dp[][]) {
        dp[from][cost]=true;
        Set<Edge> nextNodes = adjacents.get(from);
        if(nextNodes != null) {
            for(Edge e : nextNodes) {
                int newCost = cost | e.cost;
                if(!dp[e.target][newCost]) {
                    dfs(e.target, newCost, adjacents, dp);
                }
            }
        }
        
    }
    
    private static Map<Integer, Set<Edge>> makeAdjacencyList(int[][] edges) {
        Map<Integer, Set<Edge>> adjacents = new HashMap<>();
        for(int[] edge : edges) {
            int u = edge[0];
            int v = edge[1];
            int weight = edge[2];
            //System.err.format("adding %s,%s = %s\n", u, v, weight);
            if(!adjacents.containsKey(u)) adjacents.put(u, new HashSet<>());
            adjacents.get(u).add(new Edge(v,weight));
            if(!adjacents.containsKey(v)) adjacents.put(v, new HashSet<>());
            adjacents.get(v).add(new Edge(u,weight));
        }
        return adjacents;
    }
    
    private static class Edge {
        Edge(int target, int cost) {this.target = target; this.cost=cost;}
        int target;
        int cost;
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();
        int[][] edges = new int[m][3];
        for(int edges_i = 0; edges_i < m; edges_i++){
            for(int edges_j = 0; edges_j < 3; edges_j++){
                edges[edges_i][edges_j] = in.nextInt();
            }
        }
        int A = in.nextInt();
        int B = in.nextInt();
        int result = beautifulPath(edges, A, B);
        System.out.println(result);
        in.close();
    }
}

Minimum Penalty Path JavaScript Solution

'use strict';

const fs = require('fs');

process.stdin.resume();
process.stdin.setEncoding('utf-8');

let inputString = '';
let currentLine = 0;

process.stdin.on('data', function(inputStdin) {
    inputString += inputStdin;
});

process.stdin.on('end', function() {
    inputString = inputString.split('\n');

    main();
});

function readLine() {
    return inputString[currentLine++];
}

const connect = (g, u, v, c) => {
  let adj = g[u];
  if (!adj) {
    adj = []
    g[u] = adj;
  }
  adj.push({v, c});
};

/*
 * Complete the 'beautifulPath' function below.
 *
 * The function is expected to return an INTEGER.
 * The function accepts following parameters:
 *  1. 2D_INTEGER_ARRAY edges
 *  2. INTEGER A
 *  3. INTEGER B
 */

function beautifulPath(edges, A, B) {
    // console.log({edges});
    const set = new Set();
    edges.forEach(([from, to]) => {
      set.add(from);
      set.add(to);
    });
    // console.log({set});
    const g = new Array(set.size);
    for (const [u, v, c] of edges) {
      connect(g, u - 1, v - 1, c);
      connect(g, v - 1, u - 1, c);
    }
    // console.log(g);
    const N = 1000;//set.size;
    const dist = new Array(N).fill(Infinity);
    const start = A - 1;
    const end = B - 1;
    
    const visited = new Array(N);
    for (let i = 0; i < N; i++) {
      visited[i] = new Array(1024).fill(false);
    }
    
    let min = Infinity;
    const f = (u, cost) => {
      visited[u][cost] = true;
      if (u === end) {
        min = Math.min(min, cost);
        // return;
      }
      const adj = g[u];
      if (adj) {
        for (const {v, c} of adj) {
          const vc = c | cost;
          if (!visited[v][vc]) {
            f(v, vc);
          }
        }
      }
    };
    
    f(start, 0);
    for (let i = 0; i < 1024; i++) {
      const result = visited[end][i];
      if (result) {
        return i;
      }
    }
    return -1;
    
    // return min === Infinity ? -1 : min;
}

function main() {
    const ws = fs.createWriteStream(process.env.OUTPUT_PATH);

    const firstMultipleInput = readLine().replace(/\s+$/g, '').split(' ');

    const n = parseInt(firstMultipleInput[0], 10);

    const m = parseInt(firstMultipleInput[1], 10);

    let edges = Array(m);

    for (let i = 0; i < m; i++) {
        edges[i] = readLine().replace(/\s+$/g, '').split(' ').map(edgesTemp => parseInt(edgesTemp, 10));
    }

    const secondMultipleInput = readLine().replace(/\s+$/g, '').split(' ');

    const A = parseInt(secondMultipleInput[0], 10);

    const B = parseInt(secondMultipleInput[1], 10);

    const result = beautifulPath(edges, A, B);

    ws.write(result + '\n');

    ws.end();
}