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 EXISTS\n";
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("%u\n", Costs[Station_Cnt]);
}
free(Graph);
return 0;
}
0 Comments