Algorithm

HackerRank/Graph Theory/Synchronous Shopping

Problem Summary

Given a map with N shopping centers and M bidirectional roads. Each road connects two distinct shopping centers and has a travel time. There are K different kinds of fish sold in these centers, and each center may have different kinds of fish.

Two cats travel from center 1 to center N, and they want to collectively purchase all K types of fish in a minimal amount of time. Any purchase costs no time. Their paths are not necessarily the same. The total shopping time is the maximum of two cats’ shopping times. Find the minimal total shopping time.
(2 ≤ N ≤ 1000 , 1 ≤ M ≤ 2000 , 0 ≤ K ≤ 10)

Solution

Let us denote the state as (V,F), where V is the index of the current shopping center, and F is a bitmask denoting the kinds of fish already bought.

We can use Dijkstra’s algorithm to find the minimal time to reach each state (V,F), which we call cost[V,F].

Then, we enumerate F1 and F2, the bitmask of cat 1 and cat 2 when they reach N. If F1 or F2 equals 2^K - 1, we can update the answer with max(cost[N,F1],cost[N,F2]).

Theoretically, the time complexity of Dijkstra’s algorithm is O((N × 2^K)^2), since there can be at most N × (2^K) states. But the graph is sparse, and we can use adjacency list and C++’s set container to largely reduce the time complexity.

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
#include <cstdio>
#include <iostream>
#include <vector>
#include <climits>
#include <set>
#include <utility>  /* pair */
using namespace std;
const int maxn = 1030;
int n,m,kk,tot;
int fish[maxn],cost[maxn][maxn];
vector<pair<int,int> > g[maxn];
set<pair<int,pair<int,int> > > q;
void update(int x,int y,int z)
{
	if(cost[x][y]<=z) return;
	pair<int,pair<int,int> > cur = make_pair(cost[x][y],make_pair(x,y));
	set<pair<int,pair<int,int> > >::iterator it = q.find(cur);
	if(it != q.end())
		q.erase(it);
	cost[x][y]=z;
	cur.first=z;
	q.insert(cur);
}
void init()
{
	for(int i=1;i<=n;i++)
		for(int j=0;j<tot;j++)
			cost[i][j]=INT_MAX;
}
void dij()
{
	init();
	update(1,fish[1],0);
	int x,y,z;
	pair<int,int> tmp;
	set<pair<int,pair<int,int> > >::iterator it;
	while(q.size())
	{
		it = q.begin();
		z = it->first;
		x = it->second.first;
		y = it->second.second;
		q.erase(q.begin());
		for(int i=0;i<g[x].size();i++)
		{
			tmp = g[x][i];
			update(tmp.first,y|fish[tmp.first],z+tmp.second);
		}
	}
}
int main() {
	freopen("a.in","r",stdin);
	int x,y,z;
	scanf("%d%d%d",&n,&m,&kk);
	tot = 1<<kk;
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&x);
		for(int j=1;j<=x;j++)
		{
			scanf("%d",&z);
			fish[i]|=(1<<(z-1));
		}
	}
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d%d",&x,&y,&z);
		g[x].push_back(make_pair(y,z));
		g[y].push_back(make_pair(x,z));
	}
	dij();
	int ans = INT_MAX;
	for(int i=0;i<tot;i++)
		for(int j=i;j<tot;j++)
			if((j|i)==tot-1)
			{
				if(cost[n][i]>cost[n][j])
					x=cost[n][i];
				else
					x=cost[n][j];
				if(x<ans) ans=x;
			}
	printf("%d\n", ans);
    return 0;
}