斯坦纳树
<pre><code class="language-cpp">#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;
typedef pair<int, int> P;
const int maxn = 110;
vector<P> mp[maxn];
priority_queue<P, vector<P>, greater<P> > que;
int id[maxn];
bool vis[maxn];
int dp[maxn][1 << 10];
int n, m, k, x, y;
void dijkstra(int s){
memset(vis, false, sizeof(vis));
while(!que.empty()){
int u = que.top().second;
que.pop();
if(vis[u]) continue;
vis[u] = true;
for(int i = 0; i < mp[u].size(); i++){
int to = mp[u][i].second;
int w = mp[u][i].first;
if(dp[to][s] > dp[u][s] + w){
dp[to][s] = dp[u][s] + w;
que.push(P(dp[to][s], to));
}
}
}
}
int main(){
scanf("%d%d%d%d%d", &n, &m, &k, &x, &y);
id[x] = k + 1, id[y] = k + 2, k += 2;
int num = k;
for(int i = 1; i <= n; i++){
int t;
scanf("%d", &t);
if (i == x || i == y) continue;
if(t == 0) id[i] = ++num;
else id[i] = t;
}
n = num;
for(int i = 1; i <= m; i++){
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
if(id[u] == id[v]) continue;
mp[id[u]].push_back(P(w, id[v]));
mp[id[v]].push_back(P(w, id[u]));
}
memset(dp, 0x3f, sizeof(dp));
for(int i = 1; i <= k; i++) dp[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] != 0x3f3f3f3f) que.push(P(dp[i][s], i));
}
dijkstra(s);
}
printf("%d", dp[1][(1 << k) - 1]);
return 0;
}</code></pre>