Synchronous Shopping HackerRank Solution in C, CPP, Python

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

#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)