【题解】HackerRank - synchronous-shopping

Posted on In Disqus:

题目

https://www.hackerrank.com/challenges/synchronous-shopping/problem

题意

有 k 种商品，简单图上每个点上有若干种商品，购买商品不需要时间，两个人同时从 1 出发最后在 n 汇合，使得两人购买的商品囊括了所有的 k 种。 注意数据范围。

题解

  • 商品肯定是见到就买，到一个点可以免费 or 该店的商品种类。
  • k 很小最多只有 10。令状态为 (u, t)，t 为已经购买的商品，然后再新的图上跑单源最短路。
  • 最后枚举两人分配到的任务去最大值的最小值。
  • 另外不用把所有边都预先建出来，跑的时候再处理，因为有些状态可能是达不到的。

代码

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
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
#define FOR(i, x, y) for (decay<decltype(y)>::type i = (x), _##i = (y); i < _##i; ++i)
#define FORD(i, x, y) for (decay<decltype(x)>::type i = (x), _##i = (y); i > _##i; --i)
#ifdef zerol
#define dbg(args...) do { cout << "\033[32;1m" << #args<< " -> "; err(args); } while (0)
#else
#define dbg(...)
#endif
void err() { cout << "\033[39;0m" << endl; }
template<typename T, typename... Args>
void err(T a, Args... args) { cout << a << ' '; err(args...); }
// -----------------------------------------------------------------------------
const int maxn = 1000 + 100;
struct P {
    int u, k, d;
    bool operator < (const P& rhs) const { return d > rhs.d; }
};
struct E {
    int to, d;
};
priority_queue<P> pq;
vector<E> G[maxn];
int b[maxn], d[maxn][maxn];
bool vis[maxn][maxn];

void go() {
    memset(d, 0x3f, sizeof d);
    d[1][b[1]] = 0;
    pq.push({1, b[1], 0});
    while (!pq.empty()) {
        P p = pq.top(); pq.pop();
        int u = p.u, k = p.k;
        if (vis[u][k]) continue;
        dbg(u, k, d[u][k]);
        vis[u][k] = 1;
        for (E& e: G[u]) {
            int v = e.to, kk = k | b[v];
            if (d[v][kk] > d[u][k] + e.d) {
                d[v][kk] = d[u][k] + e.d;
                pq.push({v, kk, d[v][kk]});
            }
        }
    }
}

int main() {
    int n, m, k;
    cin >> n >> m >> k;
    FOR (i, 1, n + 1) {
        static int k, t;
        scanf("%d", &k);
        FOR (_, 0, k) {
            scanf("%d", &t);
            b[i] |= 1 << (t - 1);
        }
    }
    FOR (_, 0, m) {
        static int u, v, d;
        scanf("%d%d%d", &u, &v, &d);
        G[u].push_back({v, d});
        G[v].push_back({u, d});
    }
    go();
    int all = (1 << k) - 1, ans = 1E9;
    FOR (i, 0, 1 << k) dbg(i, d[n][i]);
    FOR (i, 0, 1 << k)
        FOR (j, 0, 1 << k)
            if ((i | j) == all) ans = min(ans, max(d[n][i], d[n][j]));
    cout << ans << endl;
}