一张n个点m条边的无向带权图，给定k个关键点，求一颗最小斯坦纳树。c语言实现

以下是基于Dijkstra算法的C语言实现：

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define INF 0x3f3f3f3f // 定义无穷大

int n, m, k; // 节点数、边数、关键点数
int key[10001]; // 关键点数组
int dis[10001][1 << 15]; // dis[i][j]表示从关键点j的状态到达i的最小距离
bool vis[10001][1 << 15]; // vis[i][j]表示从关键点j的状态到达i是否被访问
int map[10001][10001]; // 图的邻接矩阵

int min(int a, int b) {
    return a < b ? a : b;
}

int dijkstra(int s) {
    // 初始化
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < (1 << k); j++) {
            dis[i][j] = INF;
            vis[i][j] = false;
        }
    }
    dis[s][1 << (k - 1)] = 0; // 起点到自身状态为111...1的距离为0

    while (true) {
        // 找到当前未访问的最小距离节点
        int u = -1, min_dis = INF, status = -1;
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < (1 << k); j++) {
                if (!vis[i][j] && dis[i][j] < min_dis) {
                    u = i;
                    min_dis = dis[i][j];
                    status = j;
                }
            }
        }
        if (u == -1) break;
        vis[u][status] = true;

        // 更新未访问节点的距离
        for (int v = 1; v <= n; v++) {
            int new_status = status;
            if (key[v]) new_status |= (1 << (key[v] - 1)); // 若节点v为关键点，则更新状态
            dis[v][new_status] = min(dis[v][new_status], dis[u][status] + map[u][v]);
        }
    }

    int ans = INF;
    for (int i = 1; i <= n; i++) {
        if (i == s) continue;
        if (key[i]) ans = min(ans, dis[i][(1 << k) - 1]); // 答案为状态为111...1的最小值
    }
    return ans;
}

int main() {
    scanf("%d %d %d", &n, &m, &k);
    for (int i = 1; i <= k; i++) {
        scanf("%d", &key[i]);
    }
    for (int i = 1; i <= m; i++) {
        int u, v, w;
        scanf("%d %d %d", &u, &v, &w);
        map[u][v] = map[v][u] = w;
    }

    int ans = INF;
    for (int i = 1; i <= k; i++) {
        ans = min(ans, dijkstra(key[i])); // 对每个关键点进行Dijkstra算法
    }
    printf("%d\n", ans);

    return 0;
}

时间复杂度为$O(n^2 \times 2^k)$，其中$n$为节点数，$k$为关键点数。