算法
(bit dp) $O(2^k k^2 + k(n + m))$
可以先模拟一下样例1
- 由于 $k$ 很小(最多17个),并且我们只对序列中的 $k$ 个数字感兴趣,因此我们将对问题进行建模以利用这一部分。
- 我们将问题建模为一张图,并在 $(u, v)$之间添加一条边,如果它们可以彼此相邻,则边权为 $1$。
- 如果图中未连接 $k$ 种宝石,则答案为
-1
,否则,总会有答案。 - 约定集合 $c = \{c1, c2, \cdots, c_k\}$,$s$ 为 $c$ 的子集,$i$ 为 $s$ 中的顶点
- 令 $dist(i, j)$ 为节点 $i$ 和 节点 $c_j$ 之间的最短路径,我们可以从每个 $c_j$ 开始 $bfs$ 可以求出。
- 定义状态:$\color{red}{dp[s][i]}$:包含 $s$ 的各顶点且以顶点 $i$ 结尾的最短路径
- 转移方程:$\displaystyle dp[s][i] = \min_j \{dp[s - \text{\} \{i\}][j] + dist(i, j)\}$
- 边界情况:$dp[\{i\}][i] = 0$
C++ 代码
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using std::cin;
using std::cout;
using std::min;
using std::vector;
using std::queue;
void chmin(int& x, int y) { x = min(x, y); }
int main() {
int n, m;
cin >> n >> m;
vector<vector<int>> to(n);
rep(i, m) {
int a, b;
cin >> a >> b;
--a, --b;
to[a].push_back(b);
to[b].push_back(a);
}
int k;
cin >> k;
vector<int> c(k);
rep(i, k) {
cin >> c[i];
c[i]--;
}
vector<vector<int>> dist(k, vector<int>(k));
const int INF = 1001001001;
auto bfs = [&](int sv) {
vector<int> dist(n, INF);
queue<int> q;
dist[sv] = 0;
q.push(sv);
while (!q.empty()) {
int v = q.front(); q.pop();
for (int u : to[v]) {
if (dist[u] != INF) continue;
dist[u] = dist[v] + 1;
q.push(u);
}
}
return dist;
};
rep(i, k) {
vector<int> d = bfs(c[i]);
rep(j, k) dist[i][j] = d[c[j]];
}
int k2 = 1 << k;
vector dp(k2, vector<int>(k, INF));
rep(i, k) dp[1 << i][i] = 1;
rep(s, k2)rep(i, k) {
if (~s >> i & 1) continue;
rep(j, k) {
if (s >> j & 1) continue;
chmin(dp[s | 1<<j][j], dp[s][i] + dist[i][j]);
}
}
int ans = INF;
rep(i, k) chmin(ans, dp[k2 - 1][i]);
if (ans == INF) cout << "-1\n";
else cout << ans << '\n';
return 0;
}
nick!