最小斯坦纳树，就是要花费最小的代价，连通给定的 k 个关键点，这是一个组合优化问题。
这个问题可以用状压 DP 来解决，首先容易发现一个结论：
答案的子图一定是树。
证明：如果答案存在环，则删去环上任意一条边，代价变小。
于是我们为这棵树钦定一个树根，设 dp(i,S) 表示以 i 为根的一棵树，包含集合 S 中所有点的最小代价。
考虑如何不重不漏地转移。
一棵以 i 为根的树有两种情况，第一种是 i 的度数为 1，另一种是 i 的度数大于 1。
对于 i 的度数为 1 的情况，可以考虑枚举树上与 i 相邻的点 j，则：
dp(j,S)+w(j,i)\to dp(i,S)
对于 i 的度数大于 1 的情况，可以划分成几个子树考虑，即：
dp(i,T)+dp(i,S-T)\to dp(i,S)\ \ (T\subseteq S)
这里的转移顺序是有讲究的，这可以理解成一个类似背包的 DP，与 i 相邻的点是一个个出现的，每次多合并上一个点，所以按 S 升序枚举即可。
这两种转移具体如何实现呢？对于下面一种较为简单，枚举子集即可，时间复杂度为 O(n\times 3^k)，因为 \sum\limits_{S\subseteq\{1,\ldots,n\}} |S| 是 O(3^n) 的。
对于上面一种，其实可以想到最短路模型的三角形不等式，对于每个 S，将图做一次松弛操作即可。
由于我不喜欢 SPFA，所以这里采用了 dijkstra 实现，这部分时间复杂度为 O(m\log m\times 2^k)。
所以总时间复杂度为 O(n\times 3^k+m\log m\times 2^k)。