HackerRank Jack goes to Rapture problem solution

In this HackerRank Jack goes to Rapture problem solution you have 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.

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))

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