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 *head = NULL;
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){
head = tail = temp;
return;
}
tail->next = temp;
tail = temp;
}
void *Dequeue(){
if(head == NULL){
printf("Queue is Empty\n");
return 0;
}
struct Node *temp = head;
if(head == tail){
head = tail = NULL;
}else{
head = head->next;
}
void *d = temp->data;
free(temp);
return d;
}
int IsEmpty(){
if(head == NULL){
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];
int shortest_path[n][max_mask];
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));
read_fishmonger(fs, n);
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[0].types};
Enqueue(&start);
shortest_path[0][fs[0].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];
int mask[N];
vector<pii> g[N];
set<pair<int, pii> > q;
void go(){
dis[1][mask[1]] = 0;
q.insert(mp(dis[1][mask[1]], mp(1, mask[1])));
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 nmask = msk | mask[y];
if(vis[y][nmask]) continue;
int ndis = dis[x][msk] + w;
if(ndis < dis[y][nmask]){
dis[y][nmask] = ndis;
q.insert(mp(dis[y][nmask], mp(y, nmask)));
}
}
}
}
int main(){
sd3(n,m,k);
for(int i = 1; i <= n; i++){
int ti;
sd(ti);
int x;
while(ti--){
sd(x); x--;
mask[i] |= (1 << 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[1])]
while queue:
path_len, v, f = heappop(queue)
if A[v] is None:
if v == n:
if check(r,f,g): return path_len
r.add(f)
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
r.add(f)
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)
Aayush Kumar Gupta is the founder and creator of ExploringBits, a website dedicated to providing useful content for people passionate about Engineering and Technology. Aayush has completed his Bachelor of Technology (Computer Science & Engineering) from 2018-2022. From July 2022, Aayush has been working as a full-time Devops Engineer.
