# Synchronous Shopping HackerRank Solution in C, CPP, Python

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  (each of the centers is numbered consecutively from  to ). 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 . Their paths may intersect, they may backtrack through shopping center , and one may arrive at a different time than the other. The minimum time to determine is when both have arrived at the destination.

For example, there are  shopping centers selling  types of fish. The following is a graph that shows a possible layout of the shopping centers connected by  paths. Each of the centers is labeled . Here  and  represent Big Cat and Little Cat, respectively. In this example, both cats take the same path, i.e.  and arrive at time  having purchased all three types of fish they want. Neither cat visits shopping centers  or.

Function Description

Complete the shop function in the editor below. It should return an integer that represents the minimum time required for their shopping.

shop has the following parameters:
– n: an integer, the number of shopping centers
– k: an integer, the number of types of fish
– centers: an array of strings of space-separated integers where the first integer of each element is the number of types of fish sold at a center and the remainder are the types sold
– roads: a 2-dimensional array of integers where the first two values are the shopping centers connected by the bi-directional road, and the third is the travel time for that road

Input Format

The first line contains  space-separated integers:  (the number of shopping centers),  (the number of roads), and  (the number of types of fish sold in Bitville), respectively.

Each line  of the  subsequent lines () describes a shopping center as a line of space-separated integers. Each line takes the following form:

• The first integer, , denotes the number of types of fish that are sold by the fishmonger at the  shopping center.
• Each of the  subsequent integers on the line describes a type of fish sold by that fishmonger, denoted by , where  going forward.

Each line  of the  subsequent lines () contains  space-separated integers that describe a road. The first two integers,  and , describe the two shopping centers it connects. The third integer, , denotes the amount of time it takes to travel the road.

Output Format

Print the minimum amount of time it will take for the cats to collectively purchase all  fish and meet up at shopping center .

Sample Input

5 5 5
1 1
1 2
1 3
1 4
1 5
1 2 10
1 3 10
2 4 10
3 5 10
4 5 10


Sample Output

30


Explanation

represents a location Big Cat visits,  represents a location where Little Cat visits.

Big Cat can travel  and buy fish at all of the shopping centers on his way.

Little Cat can then travel , and buy fish from the fishmonger at the  shopping center only.

### Synchronous Shopping HackerRank Solution in C

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#include <limits.h>

struct Node {
void *data;
struct Node *next;
};

struct Node *tail = NULL;

void Enqueue(void *d){
struct Node *temp = malloc(sizeof(struct Node));
temp->data = d;
temp->next = NULL;
if(head == NULL && tail == NULL){
return;
}
tail->next = temp;
tail = temp;
}

void *Dequeue(){
printf("Queue is Empty\n");
return 0;
}
}else{
}
void *d = temp->data;
free(temp);
return d;
}

int IsEmpty(){
return 1;
}
return 0;
}

struct Fishmonger{
int num;
int types;
};

struct Edge{
int vex;
int cost;
struct Edge *next;
};

struct Vextypes{
int vex;
int types;
};

void read_fishmonger(struct Fishmonger *fm, int n){
for(int i = 0; i < n; i++){
scanf("%d", &fm[i].num);
fm[i].types = 0;
for(int j = 0; j < fm[i].num; j++){
int t;
scanf("%d", &t);
fm[i].types |= 1 << (t - 1);
}
}
}

void append(struct Edge **graph, int i, int v, int t){
struct Edge *tmp = malloc(sizeof(struct Edge));
tmp->vex = v;
tmp->cost = t;
tmp->next = NULL;
if(graph[i] == NULL){
graph[i] = tmp;
}else{
struct Edge *next = graph[i];
while(next != NULL){
struct Edge *pre = next;
next = next->next;
if(next == NULL){
pre->next = tmp;
break;
}
}
}
}

int min(int a, int b){
return a > b ? b : a;
}

int max(int a, int b){
return a < b ? b : a;
}

int main() {

/* Enter your code here. Read input from STDIN. Print output to STDOUT */
int n,m,k;
scanf("%d %d %d", &n, &m, &k);
int max_mask = 1 << k;
int dis[n];
for(int i = 0; i < n; i++){
dis[i] = INT_MAX / 2;
for(int j = 0; j < max_mask; j++){
shortest_path[i][j] = INT_MAX / 2;
}
}
struct Fishmonger *fs = malloc(n * sizeof(struct Fishmonger));
struct Edge *graph[n];
for(int i = 0; i< n; i++){
graph[i] = NULL;
}
for(int i = 0; i < m; i++){
int x,y,t;
scanf("%d %d %d", &x, &y, &t);
append(graph, x-1, y-1, t);
append(graph, y-1, x-1, t);
}
//起点加入队列
struct Vextypes start = {0,fs.types};
Enqueue(&start);
shortest_path[fs.types] = 0;
while(!IsEmpty()){
struct Vextypes *from = (struct Vextypes*)Dequeue();
struct Edge *edge = graph[from->vex];
//遍历所有邻边
while(edge != NULL){
int cost = edge->cost;
int to = edge->vex;
int types = fs[to].types | from->types;
if(shortest_path[to][types] > shortest_path[from->vex][from->types] + cost){
shortest_path[to][types] = shortest_path[from->vex][from->types] + cost;
struct Vextypes *vt = malloc(sizeof(struct Vextypes));
vt->vex = to;
vt->types = types;
//只要找到花费时间更小的边就入队对应的节点
Enqueue(vt);
}
edge = edge->next;
}
}
//从所有终点的最短路径中找到能一起凑齐所有类型的最短路径
int min_cost = INT_MAX;
for(int i = 0; i < max_mask; i++){
//printf("%d=%d\n", i, shortest_path[n-1][i]);
for(int j = i; j < max_mask; j++){
if((i | j) == max_mask - 1){
min_cost = min(min_cost, max(shortest_path[n-1][i], shortest_path[n-1][j]));
}
}
}
printf("%d", min_cost);
return 0;
}

### Synchronous Shopping HackerRank Solution CPP

#include <bits/stdc++.h>

#define sd(x) scanf("%d",&x)
#define sd2(x,y) scanf("%d%d",&x,&y)
#define sd3(x,y,z) scanf("%d%d%d",&x,&y,&z)

#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define foreach(it, v) for(__typeof((v).begin()) it=(v).begin(); it != (v).end(); ++it)
#define meta __FUNCTION__,__LINE__

#define _ ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define __ freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);

using namespace std;

template<typename S, typename T>
ostream& operator<<(ostream& out,pair<S,T> const& p){out<<'('<<p.fi<<", "<<p.se<<')';return out;}

template<typename T>
ostream& operator<<(ostream& out,vector<T> const& v){
int l=v.size();for(int i=0;i<l-1;i++)out<<v[i]<<' ';if(l>0)out<<v[l-1];return out;}

void tr(){cout << endl;}
template<typename S, typename ... Strings>
void tr(S x, const Strings&... rest){cout<<x<<' ';tr(rest...);}

typedef long long ll;
typedef pair<int,int> pii;

const long double PI = 3.1415926535897932384626433832795;

const int N = 1010;
const int M = 11;
const int INF = 1e9;

int n, m, k;

int dis[N][1<<M];
int vis[N][1<<M];
vector<pii> g[N];

set<pair<int, pii> > q;

void go(){

while(!q.empty()){
pair<int, pii> top = *q.begin();
q.erase(q.begin());

int x = top.se.fi;
int msk = top.se.se;

if(vis[x][msk]) continue;
vis[x][msk] = 1;
dis[x][msk] = top.fi;

foreach(it, g[x]){
int y = it->fi, w = it->se;

int ndis = dis[x][msk] + w;
}
}
}
}

int main(){
sd3(n,m,k);

for(int i = 1; i <= n; i++){
int ti;
sd(ti);
int x;
while(ti--){
sd(x); x--;
}
}

for(int i = 1; i <= m; i++){
int u, v, t;
sd3(u,v,t);
g[u].pb(mp(v,t));
g[v].pb(mp(u,t));
}

for(int i = 1; i <= n; i++){
for(int j = 0; j < (1 << k); j++){
dis[i][j] = INF;
}
}

go();

int ans = INF;

for(int i = 0; i < (1 << k); i++){
for(int j = 0; j < (1 << k); j++){
if((i|j) == ((1 << k) - 1)){
ans = min(ans, max(dis[n][i], dis[n][j]));
}
}
}

printf("%d\n", ans);

return 0;
}

### Synchronous Shopping HackerRank Solution Python

from heapq import heappush, heappop

def Dijkstra(graph, start, n):
A = [None] * (n+1)
queue = [(0, start)]
while queue:
path_len, v = heappop(queue)
if A[v] is None:
A[v] = path_len
for w, edge_len in graph[v].items():
if A[w] is None:
heappush(queue, (path_len + edge_len, w))
return A

def l2i(l):
r = 0
for x in l: r += 1<<(x-1)
return r

def check(r,f,g):
if f == g: return True
for x in r:
if x | f == g: return True
return False

def solve(n,m,k,ds,graph):
r = set()
g = 2 ** k - 1
A = [None] * (n+1)
queue = [(0, 1, ds)]
while queue:
path_len, v, f = heappop(queue)
if A[v] is None:
if v == n:
if check(r,f,g): return path_len
A[v] = {f:path_len}
for w, edge_len in graph[v].items():
nf = f | ds[w]
if A[w] is None or nf not in A[w]:
heappush(queue, (path_len + edge_len, w, nf))
elif f not in A[v]:
if v == n:
if check(r,f,g): return path_len
A[v][f] = path_len
for w, edge_len in graph[v].items():
nf = f | ds[w]
if A[w] is None or nf not in A[w]:
heappush(queue, (path_len + edge_len, w, nf))

n,m,k = map(int,raw_input().strip().split())
dsl = {}
ds = {}
for i in xrange(n):
l = map(int,raw_input().strip().split())[1:]
dsl[i+1] = set(l)
ds[i+1] = l2i(l)

graph = {i:{} for i in xrange(1,n+1)}
for i in xrange(m):
x,y,z = map(int,raw_input().strip().split())
graph[x][y] = z
graph[y][x] = z
print solve(n,m,k,ds,graph)