HackerRank Jack goes to Rapture Problem Solution

In this post, we will solve 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.
Example
g_nodes 4
9 from [1,1,2,3]
g_to= [2, 3, 4, 4]
g_weight [20, 5, 30, 40]

Travel from station 1 →2→ 4 costs 20 for the first segment (12) then the cost
differential, an additional 30-20= 10 for the remainder. The total cost is 30.
Travel from station 134 costs 5 for the first segment, then an additional 40-5=35
for the remainder, a total cost of 40.
The lower priced option costs 30.
Function Description
Complete the getcost function in the editor below.
getCost has the following parameters:

int g nodes: the number of stations in the network
intg fromig edges]: end stations of a bidirectional connection
int g_toig edges]: g_from[i] is connected to g_to[i] at cost g_weight[i]
int g_weight[g edges]: the cost of travel between associated stations

Prints
-int or string: the cost of the lowest priced route from station 1 to station g_nodes or NO
PATH EXISTS. No return value is expected.

Input Format
The first line contains two space-separated integers, g_nodes and g_edges, the number of stations and the number of connections between them. Each of the next g edges lines contains three space-separated integers, g_from, g_to and g_weight, the connected stations and the fare between them.

HackerRank Jack goes to Rapture Problem Solution

Jack goes to Rapture C Solution

#include <stdio.h>
#include <stdlib.h>

struct roads
{
    int city;
    int fare;
    struct roads *next;
} *cities[50001];

struct calc
{
    int city;
    int money;
} dis[50001];

int pos[50001], n, num, visited[50001];

void Heapify(int j)
{
    int i, temp;
    if(j>1)
    {
        i = j/2;
        if(dis[i].money>dis[j].money || dis[i].money==1000000000)
        {
            pos[dis[i].city] = j;
            pos[dis[j].city] = i;

            temp = dis[i].city;
            dis[i].city = dis[j].city;
            dis[j].city = temp;

            temp = dis[i].money;
            dis[i].money = dis[j].money;
            dis[j].money = temp;

            Heapify(i);
        }
    }
}

void Heapifydown(int i)
{
    int min, temp, p;
    if(2*i<=num)
    {
        min = dis[2*i].money;
        p = 2*i;

        if(p+1<=num && dis[p+1].money<min)
        {
            min = dis[p+1].money;
            p = p+1;
        }
        if(dis[p].money<dis[i].money)
        {
            pos[dis[p].city] = i;
            pos[dis[i].city] = p;

            temp = dis[i].city;
            dis[i].city = dis[p].city;
            dis[p].city = temp;

            temp = dis[i].money;
            dis[i].money = dis[p].money;
            dis[p].money = temp;
            Heapifydown(p);
        }
    }
}

void extractmin()
{
    dis[1].city = dis[num].city;
    pos[dis[num].city] = 1;
    dis[1].money = dis[num].money;
    num--;
    Heapifydown(1);
}

void dij()
{
    int i, top, ctr, temp_cost, c;
    struct roads *temp;
    dis[1].city = 1;
    dis[1].money = 0;
    pos[1] = 1;

    for(i=2; i<=n; i++)
    {
        dis[i].city = i;
        dis[i].money = 1000000000;
        pos[i] = i;
    }

    top = dis[1].city;
    num = n;
    ctr = 0;
    while(top!=n && dis[1].money!=1000000000)
    {
        temp = cities[top];
        visited[dis[1].city] = 1;
        while(temp!=NULL)
        {
            temp_cost = dis[1].money;
            c = temp->fare - dis[1].money;
            if(c>0)
                temp_cost += c;
            if((temp_cost<dis[pos[temp->city]].money || dis[pos[temp->city]].money==1000000000) && visited[temp->city]==0)
            {
                dis[pos[temp->city]].money = temp_cost;
                Heapify(pos[temp->city]);
            }
            temp = temp->next;
        }
        extractmin();
        top = dis[1].city;
    }

    if(top==n && dis[1].money<1000000000)
        printf("%d", dis[1].money);
    else
        printf("NO PATH EXISTS");
}

int main()
{
    int e, i, a, b, c;
    struct roads *temp = NULL;
    scanf("%d %d", &n, &e);
    for(i=1; i<=n; i++)
    {
        cities[i] = NULL;
        visited[i] = 0;
    }

    for(i=0; i<e; i++)
    {
        scanf("%d %d %d", &a, &b, &c);

        temp = cities[a];
        cities[a] = malloc(sizeof(struct roads));
        cities[a]->city = b;
        cities[a]->fare = c;
        cities[a]->next = temp;

        temp = cities[b];
        cities[b] = malloc(sizeof(struct roads));
        cities[b]->city = a;
        cities[b]->fare = c;
        cities[b]->next = temp;
    }

    dij();

    for(i=1; i<=n; i++)
    {
        while(cities[i]!=NULL)
        {
            temp = cities[i];
            cities[i] = cities[i]->next;
            free(temp);
        }
    }
    return 0;
}

Jack goes to Rapture C++ Solution

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int N = 5e4;
int n, m;
ll cost[N];
bool vis[N];
priority_queue<pair<ll, int> > qu;
vector<pair<int, int> > g[N];

ll Dijkstra(int src, int dest) {
  for(int i=0;i<n;++i){
    cost[i] = 1LL << 60;
  }
  qu.push(make_pair(0, src));
  cost[src] = 0;
  while(!qu.empty()){
    int v = qu.top().second;
    ll c = -qu.top().first;
    qu.pop();
    if(v == dest){
      return c;
    }
    if(vis[v]){
      continue;
    }
    vis[v] = true;
    for(int i=0;i<g[v].size();++i){
      int u = g[v][i].first;
      ll nc = c + max(0LL, g[v][i].second - c);
      if(vis[u] || nc >= cost[u]){
        continue;
      }
      cost[u] = nc;
      qu.push(make_pair(-nc, u));
    }
  }
  return -1;
}

int main() {
  scanf("%d%d", &n, &m);
  int a, b, c;
  while(m--){
    scanf("%d%d%d", &a, &b, &c);
    --a, --b;
    g[a].push_back(make_pair(b, c));
    g[b].push_back(make_pair(a, c));
  }
  ll res = Dijkstra(0, n - 1);
  if(res == -1){
    puts("NO PATH EXISTS");
  }else{
    printf("%lld\n", res);
  }
  return 0;
}

Jack goes to Rapture C Sharp Solution

using System;
using System.Collections.Generic;
using System.Linq;

class Solution {
    class PriorityQueue<T> {
        struct Node {
            private readonly T _item;
            private readonly int _priority;
            
            public Node(T item, int priority) {
                _item = item;
                _priority = priority;
            }
            
            public T Item {
                get {
                    return _item;
                }
            }
            
            public int Priority {
                get {
                    return _priority;
                }
            }
        }
        
        private Node[] _items;
        private int _count;
        
        public PriorityQueue(int size) {
            _items = new Node[size];
        }
        
        public int Count {
            get {
                return _count;
            }
        }
        
        public void Add(T item, int priority) {
            if (_count == _items.Length) {
                var oldItems = _items;
                _items = new Node[_items.Length * 2];
                
                for (var i = 0; i < oldItems.Length; i++) {
                    _items[i] = oldItems[i];
                }
            }
            
            var index = _count;
            _count++;

            _items[index] = new Node(item, priority);

            var parent = Parent(index);
            while (index > 0 && _items[index].Priority < _items[parent].Priority) {
                var tmp = _items[parent];
                _items[parent] = _items[index];
                _items[index] = tmp;
                
                index = parent;
                parent = Parent(index);
            }
        }
        
        public T Dequeue(out int cost) {
            var item = _items[0].Item;
            cost = _items[0].Priority;
            
            _items[0] = _items[_count - 1];

            var index = 0;
            while (index < _count - 1) {
                var left = Left(index);
                var right = Right(index);
                
                if (left == - 1) {
                    break;
                }
                
                if (right == -1 || _items[left].Priority < _items[right].Priority) {
                    var tmp = _items[left];
                    _items[left] = _items[index];
                    _items[index] = tmp;
                    index = left;
                }
                else {
                    var tmp = _items[right];
                    _items[right] = _items[index];
                    _items[index] = tmp;
                    index = right;
                }
            }
            
            _count--;
            
            return item;
        }
        
        private int Parent(int index) {
            return (index + 1) / 2 - 1;
        }
        
        private int Left(int index) {
            var left = index * 2 + 1;
            return left < _count ? left : -1;
        }
        
        private int Right(int index) {
            var right = index * 2 + 2;
            return right < _count ? right : -1;
        }
    }
    
    static int CheapestPath(List<Tuple<int, int>>[] graph, int start, int end) {
        var next = new PriorityQueue<int>(graph.Length);
        var visited = new bool[graph.Length];
        
        next.Add(start, 0);
        
        while (next.Count > 0) {
            int cost;
            var node = next.Dequeue(out cost);
            
            if (node == end) {
                return cost;
            }
            
            visited[node] = true;
            
            foreach (var edge in graph[node]) {
                if (visited[edge.Item1]) {
                    continue;
                }

                next.Add(edge.Item1, cost + Math.Max(0, edge.Item2 - cost));
            }
        }
        
        return -1;
    }
    
    static void Main(String[] args) {
        var inputSize = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
        var nodes = inputSize[0];
        var edges = inputSize[1];
        
        var graph = new List<Tuple<int, int>>[nodes];
        
        for (var i = 0; i < nodes; i++) {
            graph[i] = new List<Tuple<int, int>>();
        }
        
        for (var i = 0; i < edges; i++) {
            var edge = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
            var src = edge[0] - 1;
            var dst = edge[1] - 1;
            var cost = edge[2];
            
            graph[src].Add(Tuple.Create(dst, cost));
            graph[dst].Add(Tuple.Create(src, cost));
        }
        
        var cheapestPath = CheapestPath(graph, 0, nodes - 1);
        Console.WriteLine(cheapestPath == -1 ? "NO PATH EXISTS" : cheapestPath.ToString());
    }
}

Jack goes to Rapture Java Solution

//package kg.my_algorithms.HackerRank;

//import static kg.my_algorithms.Mathematics.*;

import java.io.*;
import java.util.*;

public class Solution {
    public static void main(String[] args) throws IOException {
        BufferedWriter output = new BufferedWriter(new OutputStreamWriter(System.out));
        FastReader fr = new FastReader();
        int n = fr.nextInt();
        int edges = fr.nextInt();
        List<List<int[]>> graph = new ArrayList<>();
        for(int i=0;i<n;i++) graph.add(new ArrayList<>());
        for(int i=0;i<edges;i++){
            int u = fr.nextInt()-1;
            int v = fr.nextInt()-1;
            int w = fr.nextInt();
            graph.get(u).add(new int[]{v,w});
            graph.get(v).add(new int[]{u,w});
        }
        long dis = dijkstraAlgorithm(graph);
        if(dis == Long.MAX_VALUE) output.write("NO PATH EXISTS\n");
        else output.write(dis+"\n");
        output.flush();
    }
    private static long dijkstraAlgorithm(List<List<int[]>> graph){
        int n = graph.size();
        long[] shortestDistance = new long[n];
        Arrays.fill(shortestDistance,Long.MAX_VALUE);
        shortestDistance[0] = 0L;
        Queue<long[]> queue = new ArrayDeque<>();
        queue.offer(new long[]{0,0});
        while(!queue.isEmpty()){
            long[] current = queue.remove();
            int vertex = (int)current[0];
            long parentDistance = current[1];
            for(int[] edge: graph.get(vertex)){
                int child = edge[0];
                int child_weight = edge[1];
                long childDistance = parentDistance + Math.max(0,child_weight-parentDistance);
                if(shortestDistance[child] > childDistance){
                    shortestDistance[child] = childDistance;
                    queue.offer(new long[]{child,shortestDistance[child]});
                }
            }
        }
        return shortestDistance[n-1];
    }
}

class FastReader {
    BufferedReader br;
    StringTokenizer st;

    public FastReader()
    {
        br = new BufferedReader(new InputStreamReader(System.in));
    }

    String next() {
        while (st == null || !st.hasMoreElements()) {
            try {
                st = new StringTokenizer(br.readLine());
            }
            catch (IOException e) {
                e.printStackTrace();
            }
        }
        return st.nextToken();
    }

    int nextInt() { return Integer.parseInt(next()); }

    long nextLong() { return Long.parseLong(next()); }

    double nextDouble()
    {
        return Double.parseDouble(next());
    }

    String nextLine()
    {
        String str = "";
        try {
            if(st.hasMoreTokens()){
                str = st.nextToken("\n");
            }
            else{
                str = br.readLine();
            }
        }
        catch (IOException e) {
            e.printStackTrace();
        }
        return str;
    }
}

Jack goes to Rapture JavaScript Solution

'use strict';

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

/*
 * Complete the 'getCost' function below.
 *
 * The function accepts WEIGHTED_INTEGER_GRAPH g as parameter.
 */

/*
 * For the weighted graph, <name>:
 *
 * 1. The number of nodes is <name>Nodes.
 * 2. The number of edges is <name>Edges.
 * 3. An edge exists between <name>From[i] and <name>To[i]. The weight of the edge is <name>Weight[i].
 *
 */

class PriorityQueue {
    constructor(data = [], compare = defaultCompare) {
        this.data = data;
        this.length = this.data.length;
        this.compare = compare;

        if (this.length > 0) {
            for (let i = (this.length >> 1) - 1; i >= 0; i--) this._down(i);
        }
    }

    insert(item, priority) {
        this.data.push({d: item, p: priority});
        this.length++;
        this._up(this.length - 1);
    }

    remove() {
        if (this.length === 0) return undefined;

        const top = this.data[0];
        const bottom = this.data.pop();
        this.length--;

        if (this.length > 0) {
            this.data[0] = bottom;
            this._down(0);
        }

        return top.d;
    }

    size() {
        return this.data.length;
    }

    _up(pos) {
        const {data, compare} = this;
        const item = data[pos];

        while (pos > 0) {
            const parent = (pos - 1) >> 1;
            const current = data[parent];
            if (compare(item, current) >= 0) break;
            data[pos] = current;
            pos = parent;
        }

        data[pos] = item;
    }

    _down(pos) {
        const {data, compare} = this;
        const halfLength = this.length >> 1;
        const item = data[pos];

        while (pos < halfLength) {
            let left = (pos << 1) + 1;
            let best = data[left];
            const right = left + 1;

            if (right < this.length && compare(data[right], best) < 0) {
                left = right;
                best = data[right];
            }
            if (compare(best, item) >= 0) break;

            data[pos] = best;
            pos = left;
        }

        data[pos] = item;
    }
}

function defaultCompare(a, b) {
    return a.p < b.p ? -1 : a.p > b.p ? 1 : 0;
}

function getCost(gNodes, graph) {
    // Print your answer within the function and return nothing
    
    const result = [];
    // const queue = { size: 0, set: new Set() };
    const queue = new PriorityQueue();
    
    for (let i = 1; i <= gNodes; i++) {
        result[i] = Number.MAX_SAFE_INTEGER;
    }

    result[1] = 0;
    queue.insert([1, 0], 0);

    while (queue.size() > 0) {
        const p = queue.remove();
        const v = p[0];

        const edges = graph[v];
        for (let e in edges) {
            const r = Math.max(p[1], edges[e]);

            if (result[e] > r) {
                result[e] = Math.min(result[e], r);
                queue.insert([e, r], edges[e]);
            }
        }
    }

    console.log(result[gNodes] < Number.MAX_SAFE_INTEGER ? result[gNodes] : 'NO PATH EXISTS');
}

function main() {
    const gNodesEdges = readLine().split(' ');
    
    const gNodes = parseInt(gNodesEdges[0], 10);
    const gEdges = parseInt(gNodesEdges[1], 10);

    const graph = [];
    for (let i = 1; i <= gNodes; i++) {
        graph[i] = {};
    }

    for (let i = 0; i < gEdges; i++) {
        const gFromToWeight = readLine().split(' ');

        const gFrom = parseInt(gFromToWeight[0], 10);
        const gTo = parseInt(gFromToWeight[1], 10);
        const gWeight = parseInt(gFromToWeight[2], 10);

        graph[gFrom][gTo] = gWeight;
        graph[gTo][gFrom] = gWeight;
    }

    getCost(gNodes, graph);
}

Jack goes to Rapture Python Solution

import heapq
N, E = map(int, input().split())
G = [[] for i in range(N+1)]
for e in range(E):
   A, B, C = map(int, input().split())
   G[A].append((B, C))
   G[B].append((A, C))
active = [(0, 1)]
out = 'NO PATH EXISTS'
visited = [False] * (N+1)
while len(active):
   c, i = heapq.heappop(active)
   if visited[i]: continue
   visited[i] = True
   if i == N:
      out = c
      break
   for j, d in G[i]:
      if not visited[j]:
         heapq.heappush(active, (max(c, d), j))
print(out)

c C# C++ HackerRank Solutions java javascript python C cpp CSharp Hackerrank Solutions java javascript python