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
| #include <cstdio> #include <queue> const int N = 16, M = 1 << N, K = 9, inf = 1e8; const int to[K] { 1, 2, 4, 8, 3, 12, 5, 10, 15 }; bool vis[N][M]; int A[4], d[N][M], cst[K], f[M]; struct Node { int t, s, d; Node (int _t, int _s, int _d) : t(_t), s(_s), d(_d) { } bool operator < (const Node &_) const { return d > _.d; } }; int main () { int T; scanf("%d", &T); for (int i = 0; i < 4; ++i) scanf("%d", &A[i]); for (int i = 0; i < 4; ++i) cst[i] = A[0]; for (int i = 4; i < 6; ++i) cst[i] = A[1]; for (int i = 6; i < 8; ++i) cst[i] = A[2]; cst[8] = A[3]; for (int i = 0; i < N; ++i) for (int j = 0; j < M; ++j) d[i][j] = inf; d[N - 1][0] = 0; std::priority_queue <Node> q; q.push(Node(N - 1, 0, 0)); while (!q.empty()) { int t = q.top().t, s = q.top().s; q.pop(); if (vis[t][s]) continue; vis[t][s] = true; for (int k = 0; k < 9; ++k) { int _t = t ^ to[k], _s = s | 1 << _t; if (d[_t][_s] > d[t][s] + cst[k]) q.push(Node(_t, _s, d[_t][_s] = d[t][s] + cst[k])); } } for (int i = 0; i < M; ++i) { f[i] = inf; for (int j = 0; j < N; ++j) f[i] = std::min(f[i], d[j][i]); } for (int i = 0; i < N; ++i) for (int j = 0; j < M; ++j) if (!(j >> i & 1)) f[j] = std::min(f[j], f[j ^ 1 << i]); for (int m; T; --T) { scanf("%d", &m); int s = 0; while (m--) { int t = 0; for (int i = 0, c; i < 4; ++i) scanf("%1d", &c), t |= c << i; s |= 1 << t; } printf("%d\n", f[s]); } return 0; }
|
Gitalk 加载中 ...