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();
}
Aw, this was an extremely good post. Finding the time and actual effort to generate a superb article… but what can I say… I procrastinate a lot and don’t seem to get anything done.
After looking over a few of the blog articles on your web page, I truly like your technique of blogging. I book-marked it to my bookmark site list and will be checking back soon. Please check out my web site too and let me know what you think.
Hello there! This post couldn’t be written much better! Going through this post reminds me of my previous roommate! He always kept preaching about this. I am going to forward this post to him. Fairly certain he will have a great read. Thank you for sharing!
I must thank you for the efforts you have put in penning this site. I am hoping to see the same high-grade blog posts from you later on as well. In fact, your creative writing abilities has encouraged me to get my very own website now 😉
I could not refrain from commenting. Perfectly written.