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
3 4
1 2 1
1 2 1000
2 3 3
1 3 100
1 3
Sample Output
3
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.

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();
}