引入
斯坦纳树问题，即给定一张图，选定 \(k\) 个点，求使这 \(k\) 个点联通的最小代价
不难发现，最小生成树就是最小斯坦纳树的一种特殊情况
在 \(1s\) 内可以跑过的范围大概是 \(k \leq 10, n, m \leq 10^3\) ，因为要状压，所以 \(k\) 一般不会很大
实现
首先我们可以发现答案的子图一定是树（若答案存在环，一定可以删去环上任意一边使得代价变小）
考虑设 \(f_{i, S}\) 表示以 \(i\) 为根，包含选定点的状态为 \(S\) 的情况下所需代价最小值，可得
\[f_{i, S} = \min \{ f_{i, S'} + f_{i, S \oplus S'} \}
\]
实际上就是将 \(S\) 拆分为 \(S'\) 与 \(S \oplus S'\) 两种状态，其中 \(S' \in S\)
对于新加一条边，有
\[f_{i, S} = \min \{ f_{j, S} + w \}
\]
其中 \(i, j\) 之间有一条边权为 \(w\) 的边，若 \(i\) 或 \(j\) 是关键点，则 \(S\) 一定要包含它们
注意到转移成立必须满足 \(f_{j, S} + w < f_{i, S}\) ，于是考虑用 Dijkstra 优化转移
应用
#include <bits/stdc++.h>
using namespace std;
const int inf = 0x3f3f3f3f;
const int N = 1e3 + 7, K = 13;
vector<pair<int, int> > e[N];
priority_queue<pair<int, int> > q;
int dp[N][1 << K | 1];
int p[N];
int n, m, k;
inline void AddEdge(int u, int v, int w) {
e[u].push_back(make_pair(v, w));
}
inline void Dijkstra(int S) {
while (!q.empty()) {
pair<int, int> c = q.top();
q.pop();
if (dp[c.second][S] != -c.first)
continue;
int u = c.second;
for (pair<int, int> it : e[u]) {
int v = it.first, w = it.second;
if (dp[v][S] > dp[u][S] + w) {
dp[v][S] = dp[u][S] + w;
q.push(make_pair(-dp[v][S], v));
}
}
}
}
signed main() {
scanf("%d%d%d", &n, &m, &k);
for (int i = 1, u, v, w; i <= m; ++i) {
scanf("%d%d%d", &u, &v, &w);
AddEdge(u, v, w), AddEdge(v, u, w);
}
memset(dp, inf, sizeof(dp));
for (int i = 1; i <= k; ++i) {
scanf("%d", p + i);
dp[p[i]][1 << (i - 1)] = 0;
}
for (int S = 1; S < (1 << k); ++S) {
for (int i = 1; i <= n; ++i) {
for (int subS = S & (S - 1); subS; subS = S & (subS - 1))
dp[i][S] = min(dp[i][S], dp[i][subS] + dp[i][S ^ subS]);
if (dp[i][S] != inf)
q.push(make_pair(-dp[i][S], i));
}
Dijkstra(S);
}
printf("%d", dp[p[k]][(1 << k) - 1]);
return 0;
}