n ≤ 5 個寺廟（特殊點），m ≤ 1000 個普通點，p ≤ 5000 條邊。每個點有挖井成本（點權），邊有建路成本（邊權）。寺廟需用水（連通到至少一口井）。可在任意點挖井。求最小總成本使所有寺廟連通到井。
i 連邊，權重 = 挖井成本 cost[i]。挖井等價於連通到點 0。{0} ∪ {寺廟} 的最小生成樹（斯坦納樹）。dp[full_mask][0]）。dp[mask][v]：連通狀態 mask（寺廟子集）且以 v 為根的最小成本。i（編號 1~n），dp[1<<(i-1)][i] = 0。點 0：dp[0][0] = 0？實際上點 0 是虛擬井點，所有點可通過挖井連到 0。dp[mask][v] = min(dp[sub][v] + dp[mask^sub][v])，對 mask 的所有真子集 sub。mask，在圖上跑 SPFA 傳播 dp[mask][*]（邊權為建路成本）。dp[(1<（所有寺廟連通到虛擬井點 0）。 #include <bits/stdc++.h>
using namespace std;
const int MAXV = 1005;
const int INF = 0x3f3f3f3f;
struct Edge { int to, w; };
vector G[MAXV];
int dp[1<<6][MAXV];
int dis[MAXV][MAXV];
int n, m, p;
void spfa_all() { // 多源最短路，預計算所有點對最短距離
for (int s = 0; s <= n+m; ++s) {
fill(dis[s], dis[s]+n+m+1, INF);
dis[s][s] = 0;
queue q; q.push(s);
vector inq(n+m+1); inq[s]=true;
while (!q.empty()) {
int u = q.front(); q.pop(); inq[u]=false;
for (auto& e : G[u]) {
int v = e.to;
if (dis[s][v] > dis[s][u] + e.w) {
dis[s][v] = dis[s][u] + e.w;
if (!inq[v]) q.push(v), inq[v]=true;
}
}
}
}
}
void steiner() {
int full = 1 << n;
for (int mask = 1; mask < full; ++mask) {
// 子集轉移
for (int sub = (mask-1)&mask; sub; sub = (sub-1)&mask) {
int other = mask ^ sub;
for (int v = 0; v <= n+m; ++v)
dp[mask][v] = min(dp[mask][v], dp[sub][v] + dp[other][v]);
}
// SPFA 傳播
queue q;
vector inq(n+m+1);
for (int v = 0; v <= n+m; ++v)
if (dp[mask][v] < INF) q.push(v), inq[v]=true;
while (!q.empty()) {
int u = q.front(); q.pop(); inq[u]=false;
for (auto& e : G[u]) {
int v = e.to;
if (dp[mask][v] > dp[mask][u] + e.w) {
dp[mask][v] = dp[mask][u] + e.w;
if (!inq[v]) q.push(v), inq[v]=true;
}
}
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
while (cin >> n >> m >> p) {
int V = n + m;
for (int i = 0; i <= V; ++i) G[i].clear();
// 虛擬點 0，挖井邊
for (int i = 1; i <= V; ++i) {
int c; cin >> c;
G[0].push_back({i, c});
G[i].push_back({0, c});
}
for (int i = 0; i < p; ++i) {
int a, b, c; cin >> a >> b >> c;
G[a].push_back({b, c});
G[b].push_back({a, c});
}
// 初始化 dp
for (int mask = 0; mask < (1<
複雜度
- 狀態數
2^n × V ≤ 32 × 1005 ≈ 3.2×10^4。
- 子集轉移：每個 mask 遍歷子集，總計
3^n × V（n≤5 很小）。
- SPFA：每個 mask 跑一次，總計
2^n × (V+E) ≈ 32 × 6000 ≈ 2×10^5。
- 極快，為斯坦納樹經典模板題。
關鍵點
- 虛擬點 0 統一「挖井」與「建路」。
- 子集 DP + 圖上最短路交替迭代（Dreyfus-Wagner 算法）。
- 預計算全點對最短路可優化 SPFA 為 O(1) 松弛，但 n 小時直接 SPFA 更簡潔。
