HackerRank Minimum Penalty Path problem solution

In this HackerRank Minimum Penalty Path problem solution 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.

Problem solution in Python.

#!/bin/python3

n, e = map(int, input().split())
graph = dict((i, set()) for i in range(1, n+1))
costs = [[2000]*(n+1) for i in range(0, n+1)]
for _ in range(e):
    a, b, w = map(int, input().split())
    if w < costs[a][b]:
        costs[a][b] = w
        costs[b][a] = w
        graph[a].add(b)
        graph[b].add(a)
start, end = map(int, input().split())
cost_log = [set() for j in range(n+1)]
queue = {(start, 0)}
while queue:
    (no, cost) = queue.pop()
    for ne in graph[no]:
        new_cost = costs[no][ne] | cost
        if new_cost not in cost_log[ne] and new_cost <= 1024:
            cost_log[ne].add(new_cost)
            queue.add((ne, new_cost))
print(sorted(cost_log[end])[0] if cost_log[end] else '-1')

Problem solution in Java.

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 = %sn", 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();
    }
}

Problem solution in C++.

#include<bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i = (a); i <= (b); ++i)
#define FORD(i,a,b) for(int i = (a); i >= (b); --i)
#define RI(i,n) FOR(i,1,(n))
#define REP(i,n) FOR(i,0,(n)-1)
#define mini(a,b) a=min(a,b)
#define maxi(a,b) a=max(a,b)
#define mp make_pair
#define pb push_back
#define st first
#define nd second
#define sz(w) (int) w.size()
typedef vector<int> vi;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
const int inf = 1e9 + 5;
const int nax = 1e6 + 5;

vector<pii> w[nax];
bool vis[nax];

void dfs(int a, int answer) {
	vis[a] = true;
	for(pii edge : w[a]) {
		int b = edge.first;
		if(vis[b]) continue;
		int cost = edge.second;
		if((answer | cost) == answer)
			dfs(b, answer);
	}
}

bool are_connected(int a, int b, int answer, int n) {
	RI(i, n) vis[i] = false;
	dfs(a, answer);
	return vis[b];
}

int main() {
	int n, m;
	scanf("%d%d", &n, &m);
	REP(_, m) {
		int a, b, c;
		scanf("%d%d%d", &a, &b, &c);
		w[a].pb(mp(b,c));
		w[b].pb(mp(a,c));
	}
	int x, y;
	scanf("%d%d", &x, &y);
	const int K = 10; // the maximum number of bits
	int answer = (1 << K) - 1; // 1023
	if(!are_connected(x, y, answer, n)) {
		puts("-1");
		return 0;
	}
	for(int i = K - 1; i >= 0; --i)
		if(are_connected(x, y, answer - (1 << i), n))
			answer -= 1 << i;
	printf("%dn", answer);
	return 0;
}

Problem solution in C.

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#include<stdbool.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 *ptr=(struct node *)malloc(sizeof(struct node));
    ptr->next=NULL;
    ptr->data=b;
    ptr->cost=cost;
    if(x[a]==NULL){
        x[a]=ptr;
        y[a]=ptr;
    }
    else
    {y[a]->next=ptr;
      y[a]=ptr;  
    }    
}

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 *ptr;   
 a[1]=start;
 b[1]=0;
    
 while(start1<=end1){
     i=a[start1];
     j=b[start1];
     start1++;
     ptr=x[i];
     //dp[i][j]=1;
     while(ptr!=NULL){
         if(dp[ptr->data][j|ptr->cost]==0){
             end1++;
             dp[ptr->data][j|ptr->cost]=1;
             a[end1]=ptr->data;
             b[end1]=j|ptr->cost;
         }
     ptr=ptr->next;
     }
 }   
}

int main() {

    /* Enter your code here. Read input from STDIN. Print output to STDOUT */  
    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;
}