# HackerRank Synchronous Shopping problem solution

In this HackerRank Synchronous Shopping problem solution, Bitville is a seaside city that has a number of shopping centers connected by bidirectional roads, each of which has a travel time associated with it. Each of the shopping centers may have a fishmonger who sells one or more kinds of fish. Two cats, Big Cat and Little Cat are at shopping center 1 (each of the centers is numbered consecutively from 1 to n). They have a list of fish they want to purchase, and to save time, they will divide the list between them. Determine the total travel time for the cats to purchase all of the types of fish, finally meeting at shopping center n. Their paths may intersect, they may backtrack through shopping centers n, and one may arrive at a different time than the other. The minimum time to determine is when both have arrived at the destination.

## Problem solution in Python.

```#!/bin/python3

import math
import os
import random
import re
import sys

#
# Complete the 'shop' function below.
#
# The function is expected to return an INTEGER.
# The function accepts following parameters:
#  1. INTEGER n
#  2. INTEGER k
#  3. STRING_ARRAY centers
#

from collections import deque

import heapq

all_fishes_mask = 2 ** k - 1
f = 1
for _ in range(k):
f <<= 1

cities = [0] * (n + 1)
for idx, c_str in enumerate(centers):
c_data = list(map(int, c_str.split()))
if c_data[0] > 0:
cities[idx + 1] = sum([fish_masks[i] for i in c_data[1:]])

neighbours = [[] for _ in range(n+1)]
times = [[0] * (n+1) for _ in range(n+1)]
for c1, c2, t in roads:
neighbours[c1].append(c2)
neighbours[c2].append(c1)
times[c1][c2] = t
times[c2][c1] = t

q = [(1 << 10) + cities[1]]
seen = [[False] * (all_fishes_mask + 1) for _ in range(n + 1)]
trip_time = [[None] * (all_fishes_mask + 1) for _ in range(n + 1)]

fish_mask = 2 ** 10 - 1

while q:
data = heapq.heappop(q)
time = data >> 20
node = (data & node_mask) >> 10
continue
continue
for nxt in neighbours[node]:
continue
nxt_new_time = time + times[node][nxt]
if (nxt_cur_time is not None) and (nxt_new_time >= nxt_cur_time):
continue
heapq.heappush(q, (nxt_new_time << 20) + (nxt << 10) + nxt_mew_mask)

rv = 0
trip_times = trip_time[n]
if not time_i:
continue
if not time_j:
continue
t_time = max(time_i, time_j)
continue
if rv and t_time >= rv:
continue
rv = t_time
return rv

if __name__ == '__main__':
fptr = open(os.environ['OUTPUT_PATH'], 'w')

first_multiple_input = input().rstrip().split()

n = int(first_multiple_input[0])

m = int(first_multiple_input[1])

k = int(first_multiple_input[2])

centers = []

for _ in range(n):
centers_item = input()
centers.append(centers_item)

for _ in range(m):

res = shop(n, k, centers, roads)

fptr.write(str(res) + '\n')

fptr.close()
```

{"mode":"full","isActive":false}

## Problem solution in Java.

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

public class Solution {
static class Node {
int label, time, status;
public Node(int label, int time, int status) {
this.label = label;
this.time = time;
this.status = status;
}
}

private static int minTime(int n, int k, int[] sale, List<List<Node>> graph) {
int[][] time = new int[1 << k][n];
for (int[] t : time) Arrays.fill(t, Integer.MAX_VALUE);
PriorityQueue<Node> minHeap = new PriorityQueue<>(new Comparator<Node>(){
@Override
public int compare(Node n1, Node n2) {
return n1.time - n2.time;
}
});
minHeap.offer(new Node(0, 0, sale[0]));
time[sale[0]][0] = 0;
List<Node> candidates = new ArrayList<>();
while (!minHeap.isEmpty()) {
Node cur = minHeap.poll();
if (cur.label == n - 1) candidates.add(cur);
for (Node node : graph.get(cur.label)) {
int newStatus = (cur.status | sale[node.label]);
if (cur.time + node.time < time[newStatus][node.label]) {
time[newStatus][node.label] = cur.time + node.time;
minHeap.offer(new Node(node.label, cur.time + node.time, newStatus));
}
}
}

int min = Integer.MAX_VALUE;
for (int i = 0; i < candidates.size(); i++) {
Node cur = candidates.get(i);
for (int j = i; j < candidates.size(); j++) {
Node another = candidates.get(j);
if ((cur.status | another.status) == (1 << k) - 1) {
min = Math.min(min, Math.max(cur.time, another.time));
}
}
}
return min;
}

private static final Scanner SCANNER = new Scanner(System.in);

public static void main(String[] args) {
/* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
String nmk = SCANNER.nextLine();
String[] nmkVals = nmk.split(" ");
int n = Integer.valueOf(nmkVals[0]), m = Integer.valueOf(nmkVals[1]), k = Integer.valueOf(nmkVals[2]);

int[] sale = new int[n];
for (int i = 0; i < n; i++) {
String items = SCANNER.nextLine();
String[] types = items.split(" ");
for (int j = 1; j < types.length; j++) {
sale[i] |= (1 << (Integer.valueOf(types[j]) - 1));
}
}

List<List<Node>> graph = new ArrayList<>();
for (int i = 0; i < n; i++) graph.add(new ArrayList<>());
for (int i = 0; i < m; i++) {
String edge = SCANNER.nextLine();
String[] detail = edge.split(" ");
int n1 = Integer.valueOf(detail[0]) - 1, n2 = Integer.valueOf(detail[1]) - 1, t = Integer.valueOf(detail[2]);
}

System.out.print(minTime(n, k, sale, graph));
}
}
```

{"mode":"full","isActive":false}

## Problem solution in C++.

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

#define MAX 1100
#define MOD 1000000007
#define PI 3.1415926535897932384
#define F first
#define S second
#define pb push_back
#define mp make_pair
typedef long long ll;

int cost[MAX][MAX];
int n, m, k;
vector<int> fish[MAX];

void db(int val){
vector<int> aux;

for(int i = 0;i < k;i++){
if(val & (1<<i)){aux.pb(1);}
else aux.pb(0);
}

for(int i = aux.size()-1;i >= 0;i--) cout << aux[i];
}

void prepare_spell(){
set<pair<int, pair<int, int> > > my_s;

int mask = 0, cur = 0;
for(int i = 0;i < fish[cur].size();i++){
}

while(!my_s.empty()){
pair<int, pair<int, int> >  aux = *my_s.begin();

//cout << aux.F << " " << aux.S.F << " "; db(aux.S.S); cout << endl;

my_s.erase(my_s.begin());

if(cost[aux.S.F][aux.S.S] != -1 &&
cost[aux.S.F][aux.S.S] <= aux.F) continue;

cost[aux.S.F][aux.S.S] = aux.F;

for(int i = 0;i < adj[aux.S.F].size();i++){

for(int j = 0;j < fish[adj[aux.S.F][i].F].size();j++){
}

//cout << aux.S.F << " " << adj[aux.S.F][i].F << " "; db(mask);

//cout << " aceito" << endl;
}
//else cout << " nao aceito" << endl;
}

}
}

int cast_spell(){
int aux = 0;

for(int i = 0;i < k;i++) aux |= (1<<i);

int res = -1;
for(int i = 0;i < MAX;i++){
for(int j = 0;j < MAX;j++){
if((i|j) == aux && cost[n-1][i] != -1 && cost[n-1][j] != -1 &&
(res == -1 || max(cost[n-1][i], cost[n-1][j]) < res)){
res = max(cost[n-1][i], cost[n-1][j]);
}
}
}

return res;
}

int main(){
//freopen("in", "r", stdin);
// freopen("out", "w", stdout);

cin >> n >> m >> k;

memset(cost, -1, sizeof(cost));

for(int aux, i = 0;i < n;i++){
cin >> aux;

for(int f, j = 0;j < aux;j++){
cin >> f;
fish[i].pb(f-1);
}
}

for(int a, b, c, i = 0;i < m;i++){
cin >> a >> b >> c;

}

prepare_spell();
cout << cast_spell() << endl;

return 0;
}
```

{"mode":"full","isActive":false}

## Problem solution in C.

```#include <assert.h>
#include <ctype.h>
#include <limits.h>
#include <math.h>
#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

const int MAX_INT = 1<<30;

typedef struct Item {
int key;
int value;
int node;
} Item;

typedef struct PriorityQueue {
Item* arr;
int size;
int cap;
} Queue;

Queue* initQueue() {
Queue* q = malloc(sizeof(Queue));
q->size = 0;
q->cap = 0;
q->arr = NULL;
return q;
}

void insert(Queue* q, int key, int value, int node) {
if (q->size == q->cap) {
q->cap = q->cap * 2 + 1;
q->arr = realloc(q->arr, q->cap * sizeof(Item));
}
q->arr[q->size].key = key;
q->arr[q->size].value = value;
q->arr[q->size].node = node;
q->size++;

// Up-heap
int idx = q->size - 1;
int parent_idx = (idx - 1) / 2;
while (parent_idx >= 0 && q->arr[idx].key < q->arr[parent_idx].key) {
Item t = q->arr[idx];
q->arr[idx] = q->arr[parent_idx];
q->arr[parent_idx] = t;
idx = parent_idx;
parent_idx = (idx - 1) / 2;
}
}

Item extractMin(Queue* q) {
Item item = q->arr[0];
q->arr[0] = q->arr[--q->size];

// Down-heap
int idx = 0;
int left = idx * 2 + 1;
int right = idx * 2 + 2;
while (
(left < q->size && q->arr[left].key < q->arr[idx].key) ||
(right < q->size && q->arr[left].key < q->arr[idx].key)
) {
if (
left < q->size && q->arr[left].key < q->arr[idx].key &&
(right >= q->size || q->arr[left].key < q->arr[right].key)
) {
Item t = q->arr[idx];
q->arr[idx] = q->arr[left];
q->arr[left] = t;
idx = left;
} else {
Item t = q->arr[idx];
q->arr[idx] = q->arr[right];
q->arr[right] = t;
idx = right;
}
left = idx * 2 + 1;
right = idx * 2 + 2;
}

return item;
}

int shop(int n, int k, int* t, int* B_size, int** B, int** W) {
int** shortest = malloc(n*sizeof(int*));
for (int i=0; i<n; i++) {
shortest[i] = malloc((1<<k)*sizeof(int));
for (int j=0; j<(1<<k); j++) {
shortest[i][j] = MAX_INT;
}
}

Queue* q = initQueue();
insert(q, 0, t[0], 0);
while (q->size > 0) {
Item item = extractMin(q);
int key = item.key, value=item.value, u = item.node;
// if (u == n-1) {
//     int opp = value ^ ((1<<k) - 1);
//     for (int i=0; i<=(1<<k)-1; i++) {
//         if (shortest[u][opp | i] < MAX_INT) return key;
//     }
// }
if (item.key >= shortest[u][value]) continue;
shortest[u][value] = item.key;
for (int i=0; i<B_size[u]; i++) {
int v = B[u][i], w = W[u][i];
insert(q, key + w, value | t[v], v);
}
}

int min = MAX_INT;
for (int i=0; i<(1<<k); i++) {
int cur = shortest[n-1][i];
for (int j=0; j<(1<<k); j++) {
if ((i | j) != (1<<k) - 1) continue;
int opp = shortest[n-1][j];
if (cur >= opp && min > cur) min = cur;
else if (opp >= cur && min > opp) min = opp;
}
}
return min;
}

int main()
{
FILE* fptr = fopen(getenv("OUTPUT_PATH"), "w");

int n, m, k; scanf("%d%d%d", &n, &m, &k);
int* t = malloc(n * sizeof(int));

for (int i=0; i<n; i++) {
int n_fishes; scanf("%d", &n_fishes);
t[i] = 0;
for (int _=0; _<n_fishes; _++) {
int fish; scanf("%d", &fish);
t[i] |= 1<<(fish-1);
}
}

int* B_size = malloc(n * sizeof(int)); // Vertex order
int* B_cap = malloc(n * sizeof(int)); // Capacity of B
int** B = malloc(n * sizeof(int*)); // Adjacent list
int** W = malloc(n * sizeof(int*)); // Adjacent weight

for (int i=0; i<n; i++) {
B_size[i] = 0;
B_cap[i] = 0;
B[i] = NULL;
W[i] = NULL;
}

for (int j=0; j<m; j++) {
int u, v, w; scanf("%d%d%d", &u, &v, &w);
u--; v--;

if (B_size[u] == B_cap[u]) {
B_cap[u] = B_cap[u] * 2 + 1;
B[u] = realloc(B[u], B_cap[u] * sizeof(int));
W[u] = realloc(W[u], B_cap[u] * sizeof(int));
}
B[u][B_size[u]] = v; W[u][B_size[u]] = w; B_size[u]++;

if (B_size[v] == B_cap[v]) {
B_cap[v] = B_cap[v] * 2 + 1;
B[v] = realloc(B[v], B_cap[v] * sizeof(int));
W[v] = realloc(W[v], B_cap[v] * sizeof(int));
}
B[v][B_size[v]] = u; W[v][B_size[v]] = w; B_size[v]++;
}

int res = shop(n, k, t, B_size, B, W);
fprintf(fptr, "%d\n", res);
fclose(fptr);
return 0;
}
```

{"mode":"full","isActive":false}