斯坦纳树

#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;
}