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