HackerRank Minimum Penalty Path Solution Yashwant Parihar, May 19, 2023May 19, 2023 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 CkGiven 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 FormatThe 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 FormatPrint 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 3 4 1 2 1 1 2 1000 2 3 3 1 3 100 1 3 Sample Output 3 ExplanationThe 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 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(); } c C# C++ HackerRank Solutions java javascript python CcppCSharpHackerrank Solutionsjavajavascriptpython