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 = %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();
}
}
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("%d\n", 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;
}
0 Comments