$\LARGE{题目描述}$

给定一个无向图 $G = (V, E)$ ，每一条边有一个权值。

要求一个子图 $G’$，使得给定的 $k$ 个点在子图中相互连通，且 $G’$ 上权值之和最小。

$n \leq 100, m \leq 500, k \leq 10, w \leq 10^6$。

$\LARGE{分析}$

由于子图 $G’$ 一定构成一颗树，设 $f_{i, j}$ 表示以 $i$ 为根，且连通状态为 $j$ 的权值最小值， $j$ 表示为一个二进制数。

把 $S$ 分为 $T$ 和 $T’$ ，有转移方程：

$$f_{i, S} \gets f_{i, T} + f_{i, T’}$$

若有边 $(i, j)$ ，有转移方程：

$$f_{j, S} \gets f_{i, S} + w_{i, j}$$

第一个转移式通过二进制解决，第二个转移式可以用 $dijkstra$ 转移。

$\LARGE{实现}$

#include <bits/stdc++.h>
using namespace std;

int n, m, k;
int f[110][1 << 11], s[12];
int h[110], e[1010], w[1010], ne[1010], idx;
bool vis[110];
typedef pair<int, int> PII;

void add(int a, int b, int c) {
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}

void relax(int s) {
    priority_queue<PII, vector<PII>, greater<PII>> q;
    for (int i = 1; i <= n; i ++ ) q.push({f[i][s], i});
    while (q.size()) {
        int t = q.top().second;
        q.pop();
        vis[t] = false;
        for (int i = h[t]; ~i; i = ne[i]) {
            int ver = e[i];
            if (f[ver][s] > f[t][s] + w[i]) {
                f[ver][s] = f[t][s] + w[i];
                q.push({f[ver][s], ver});
            }
        }
    }
}

int main() {
    scanf("%d%d%d", &n, &m, &k);
    memset(h, -1, sizeof h);
    for (int i = 0; i < m; i ++ ) {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c), add(b, a, c);
    }
    memset(f, 0x3f, sizeof f);
    for (int i = 0; i < k; i ++ ) scanf("%d", &s[i]), f[s[i]][1 << i] = 0;
    for (int i = 0; i < 1 << k; i ++ ) {
        for (int j = i & (i - 1); j; j = (j - 1) & i)
            for (int k = 1; k <= n; k ++ )
                f[k][i] = min(f[k][i], f[k][j] + f[k][i ^ j]);
        relax(i);
    }
    int ans = 2e9;
    for (int i = 1; i <= n; i ++ ) ans = min(ans, f[i][(1 << k) - 1]);
    printf("%d", ans);
    return 0;
}