HackerRank Jack goes to Rapture problem solution

YASH PAL,

In this HackerRank Jack goes to Rapture problem solution Jack has just moved to a new city called Rapture. He wants to use the public public transport system. The fare rules are as follows:

  • Each pair of connected stations has a fare assigned to it regardless of direction of travel.
  • If Jack travels from station A to station B, he only has to pay the difference between (the fare from A to B) and (the cumulative fare paid to reach station A), [fare(A,B) – total fare to reach station A]. If the difference is negative, travel is free of cost from A to B.

Jack is low on cash and needs your help to figure out the most cost efficient way to go from the first station to the last station. Given the number of stations g_nodes (numbered from 1 to g_nodes), and the fares (weights) between the g_edges pairs of stations that are connected, determine the lowest fare from station 1 to station g_nodes.

HackerRank Jack goes to Rapture problem solution

HackerRank Jack goes to Rapture problem solution in Python.

#!/bin/python3

import sys
from collections import defaultdict
from collections import deque

import heapq

def min_path(graph, n):
       
    costs = [10 ** 10] * (n + 1)
    work = []
    heapq.heappush(work, (0, 1))
    
    costs[1] = 0
    
    while work:
        (current_cost, current_node) = heapq.heappop(work)
        for (neighbour, cost) in graph[current_node]:
            acc_cost = max(current_cost, cost)
            if acc_cost < costs[neighbour]:
                costs[neighbour] = acc_cost
                heapq.heappush(work, (acc_cost, neighbour))
    
    return costs[n] if costs[n] < 10 ** 10 else 'NO PATH EXISTS'

if __name__ == '__main__':
    g_nodes, g_edges = map(int, input().split())
    
    graph = defaultdict(set)
    
    for _ in range(g_edges):
        start, end, cost = map(int, input().split())
        graph[start].add((end, cost))
        graph[end].add((start, cost))

    print(min_path(graph, g_nodes))

Jack goes to Rapture problem solution in Java.

import java.io.*;
import java.util.*;
public class Solution {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String[] line = br.readLine().split(" ");
        final int N = Integer.parseInt(line[0]);

        final List<List<Connection>> stations = new ArrayList<List<Connection>>(N);
        for(int i = 0; i++ < N; stations.add(new ArrayList<Connection>())){}

        //Get connections and their fares
        for(int E = Integer.parseInt(line[1]); E > 0; --E){
            line = br.readLine().split(" ");
            final int A = Integer.parseInt(line[0]) - 1;
            final int B = Integer.parseInt(line[1]) - 1;
            final int C = Integer.parseInt(line[2]);
            final Connection connection = new Connection(A, B, C);
            stations.get(A).add(connection);
            stations.get(B).add(connection);
        }

        //GC: Remove input reader
        br.close();
        br = null;

        //Get lowest fare from stations 1 to N
        final int minFare = getMinFare(stations, 0, N-1);
        System.out.println((minFare < 0) ? "NO PATH EXISTS" : minFare);
    }

    private static int getMinFare(final List<List<Connection>> stations, final int origin, final int destination){

        //Initialize min fares to max fare
        final int N = stations.size();
        final int[] minFares = new int[N];
        for(int i = 0, c = Integer.MAX_VALUE; i < N; minFares[i++] = c){}

        //Starting at origin, travel each route in min fare order until destination reached
        final Queue<Pair<Integer, Integer>> q = new PriorityQueue<Pair<Integer, Integer>>(N);
        minFares[origin] = 0;
        q.add(new Pair<Integer, Integer>(origin, 0));
        do {

            //Get current station and min fare
            final int stationId = q.poll().key;
            final int curFare = minFares[stationId];

            //If destination reached
            if(stationId == destination){
                return curFare;
            }

            //Visit connecting stations that are unvisited / could be visited cheaper
            for(Connection connection : stations.get(stationId)){
                final int connectingStationId = connection.getStationId(stationId);
                final int minFare = minFares[connectingStationId];
                final int newMinFare = Math.max(curFare, connection.fare);
                if(minFare > newMinFare){
                    minFares[connectingStationId] = newMinFare;
                    q.add(new Pair<Integer, Integer>(connectingStationId, newMinFare));
                }
            }
        } while (!q.isEmpty());

        //If destination is unreachable
        return -1;
    }

    private static class Pair<K, V extends Comparable<V>> implements Comparable<Pair<K, V>>{
        public final K key;
        public final V value;

        public Pair(final K key, final V value){
            this.key = key;
            this.value = value;
        }

        public int compareTo(Pair<K, V> b){
            return this.value.compareTo(b.value);
        }
    }

    private static class Connection {
        public final int fare;
        public final int stationIds;

        public Connection(final int stationId1, final int stationId2, final int fare){
            this.fare = fare;
            this.stationIds = stationId1 ^ stationId2;
        }

        public int getStationId(final int stationId){
            return stationIds ^ stationId;
        }
    }
}

Problem solution in C++.

#include <bits/stdc++.h>
#define ll long long
#define X first
#define Y second
#define pb push_back
#define mp make_pair
#define PII pair<long long, long long>
#define MAXM 100005

using namespace std;

class Set
{
public:
	ll rank[MAXM], parent[MAXM], machine[MAXM];
	Set()
	{
		for (int i = 0; i < MAXM; ++i)
		{
			rank[i] = 0;
			parent[i] = i;
		}
	};
	ll find( ll node )
	{
		if ( parent[node] != node )
			return find( parent[node] );
		return node;
	}
	void merge( ll node1, ll node2 )
	{
		ll parent1 = find( node1 );
		ll parent2 = find( node2 );
		if ( rank[parent1] < rank[parent2] )
			parent[ parent1 ] = parent2;
		else if ( rank[parent2] < rank[parent1] )
			parent[ parent2 ] = parent1;
		else if ( rank[ parent1 ] == rank[ parent2 ] )
		{
			parent[ parent2 ] = parent1;
			rank[parent1]++;
		}
	}
	bool isConnected( ll node1, ll node2 )
	{
		return (find(node1) == find(node2));
	}
};

std::vector< pair< long long, PII > > edge, final;
std::vector< PII > E[MAXM];
ll cost[MAXM];

void DFS( ll source, ll parent = -1 )
{
	for (int i = 0; i < E[source].size(); ++i)
	{
		if ( E[source][i].X != parent )
		{
			cost[ E[source][i].X ] = max(cost[ source ] , E[source][i].Y);
			DFS( E[source][i].X, source );
		}
	}
}

int main(int argc, char const *argv[])
{
	ll M, N, a, b, c;
	cin >> N >> M;
	memset(cost, 0, sizeof cost);
	Set S;
	for (int i = 0; i < M; ++i)
	{
		cin >> a >> b >> c;
		a--;
		b--;
		edge.pb( mp(c, mp(a, b) ) );
	}
	sort( edge.begin(), edge.end() );
	for (int i = 0; i < M; ++i)
	{
		if ( !S.isConnected( edge[i].Y.X, edge[i].Y.Y ) )
		{
			final.pb( edge[i] );
		}
		S.merge( edge[i].Y.X, edge[i].Y.Y );
	}
	for (int i = 0; i < final.size(); ++i)
	{
		E[ final[i].Y.X ].pb( mp( final[i].Y.Y, final[i].X ) );
		E[ final[i].Y.Y ].pb( mp( final[i].Y.X, final[i].X ) );
	}
	cost[0] = 0;
	DFS( 0 );
    if( cost[N-1] )
	   cout << cost[N-1] << 'n';
    else
       cout << "NO PATH EXISTSn";
	return 0;
}

Problem solution in C.

#include<stdio.h>
typedef union
{
    struct
    {
        unsigned short Source, Target;
        unsigned Cost;
    };
    unsigned long Packed;
}Edge;
int main()
{
    unsigned At, Station_Cnt, Edge_Cnt;
    scanf("%u %u", &Station_Cnt, &Edge_Cnt);
    unsigned long Indices[Station_Cnt + 1];
    for( At = Station_Cnt + 1 ; At-- ; Indices[At] = 0 );
    Edge *Graph = malloc(( sizeof(Edge) * ( Edge_Cnt << 1 ) ) | 1);
    Edge Edges[Edge_Cnt << 1];
    for( At = 0 ; At < Edge_Cnt ; At++ )
    {
        scanf("%hu %hu %u", &Edges[At].Source, &Edges[At].Target, &Edges[At].Cost);
        Edges[At + Edge_Cnt].Source = Edges[At].Target;
        Edges[At + Edge_Cnt].Target = Edges[At].Source;
        Edges[At + Edge_Cnt].Cost = Edges[At].Cost;
        Indices[Edges[At].Source]++;
        Indices[Edges[At].Target]++;
    }
    Edge_Cnt <<= 1;
    for( At = 0 ; ++At <= Station_Cnt ; Indices[At] += Indices[At - 1] );
    for( At = Edge_Cnt ; At-- ; Graph[--Indices[Edges[At].Source]].Packed = Edges[At].Packed );
    Graph[Edge_Cnt].Packed = 0;
    Indices[0] = Edge_Cnt;
    unsigned Costs[Station_Cnt + 1];
    unsigned short Vertices[Station_Cnt + 2], Locations[Station_Cnt + 2];
    for( At = 0 ; At <= ( Station_Cnt + 1 ) ; Costs[At++] = 0xFFFFFFFFU )
    {
        Vertices[At] = (unsigned short)At;
        Locations[At] = (unsigned short)At;
    }
    Costs[0] = 0;
    Costs[1] = 0;
    for( At = Station_Cnt ; At && Costs[Vertices[1]] != 0xFFFFFFFFU && Vertices[1] != Station_Cnt ; )
    {
        unsigned short Source = Vertices[1], Target = Vertices[At];
        unsigned Parent = 1, Child = 2;
        for( Vertices[At--] = (unsigned short)( Station_Cnt + 1 ) ; Child <= At ; Child <<= 1 )
        {
            Child |= ( Costs[Vertices[Child | 1]] < Costs[Vertices[Child]] );
            if( Costs[Vertices[Child]] <= Costs[Target] )
            {
                Vertices[Parent] = Vertices[Child];
                Locations[Vertices[Child]] = (unsigned short)Parent;
                Parent = Child;
            }
            else
            {
                break;
            }
        }
        Vertices[Parent] = Target;
        Locations[Target] = (unsigned short)Parent;
        Edge *Others = &Graph[Indices[Source]];
        for( Indices[Source] = Edge_Cnt ; Others -> Source == Source ; Others++ )
        {
            if( Indices[Others -> Target] != Edge_Cnt )
            {
                unsigned Cost = ( Others -> Cost > Costs[Source] ) ? Others -> Cost : Costs[Source];
                if( Cost < Costs[Others -> Target] )
                {
                    Costs[Others -> Target] = Cost;
                    for( Child = Locations[Others -> Target] ; Cost < Costs[Vertices[Child >> 1]] ; Child >>= 1 )
                    {
                        Vertices[Child] = Vertices[Child >> 1];
                        Locations[Vertices[Child]] = (unsigned short)Child;
                    }
                    Vertices[Child] = Others -> Target;
                    Locations[Others -> Target] = (unsigned short)Child;
                }
            }
        }
    }
    if( Costs[Station_Cnt] == 0xFFFFFFFFU )
    {
        printf("NO PATH EXISTS");
    }
    else
    {
        printf("%un", Costs[Station_Cnt]);
    }
    free(Graph);
    return 0;
}

Algorithms coding problems solutions