斯坦纳树，求图中 $k$ 个点联通的最小代价，相当于扩展最小生成树（我自己给的定义）。

这个算法本身其实比较 useless，但这种最短路加状压的想法还是比较巧妙的。

发现 $k$ 很小，考虑状压，设 $f_{i,S}$ 表示当前联通的关键节点集合为 $S$，联通块中有一个节点为 $i$，$i$ 是其中哪一个都一样，只是为了转移方便。

容易得到下面两个式子：

$$f_{i,S}=\min f_{i,T}+f_{i,S-T}\\ f_{i,S}=\min f_{j,S}+a_i $$

$a_i$ 表示选 $i$ 的点权，此时 $i,j$ 联通。

第一个式子可以随便做。

第二个式子第二维都是 $S$，单独把这一维拉出来，可以发现实际上满足最短路的式子。

按 $S$ 分层做，每次做一遍第一个式子，再做一遍第二个式子。

大部分人第二个式子用的都是 SPFA，但是它死了，考虑使用 dij。

其实比较简单，可以想到建立一个虚点连向所有的点，代价就是第一个式子跑出来的 $f_{i,S}$。

也可以不建虚点，开始就把距离设为 $f_{i,S}$，然后全部扔到队列中去。

输出方案也比较简单，记录一下是从哪个式子转移来的，再记一下上一个状态就好了。

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> Int;
const int N=15;
vector<int> e[N*N];
int vis[N*N],tot,f[N*N][1<<N],a[N*N],id[N][N];
Int las[N*N][1<<N];
priority_queue<Int,vector<Int>,greater<Int> > q;
void ling(int x,int y){e[x].push_back(y),e[y].push_back(x);}
void dij(int S){
    memset(vis,0,sizeof(vis));
    while(!q.empty()){
        int x=q.top().second;q.pop();
        if(vis[x])continue;
        vis[x]=1;
        for(int y:e[x]){
            if(f[x][S]+a[y]<f[y][S]){
                f[y][S]=f[x][S]+a[y];
                las[y][S]=make_pair(0,x);
                q.push(make_pair(f[y][S],y));
            }
        }
    }
}
void write(int x,int y){
    if(las[x][y].first==-1)return;
    vis[x]=1;
    if(las[x][y].first==1){
        write(x,y-las[x][y].second);
        write(x,las[x][y].second);
    }
    else write(las[x][y].second,y);
}
int n,m,cnt,ans=1e9,ans1;
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){
        id[i][j]=++tot;
        scanf("%d",&a[tot]);
        if(i>1)ling(id[i][j],id[i-1][j]);
        if(j>1)ling(id[i][j],id[i][j-1]);
    }
    memset(f,63,sizeof(f));
    for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)if(!a[id[i][j]])f[id[i][j]][1<<cnt]=0,las[id[i][j]][1<<cnt]=make_pair(-1,-1),cnt++;
    for(int S=1;S<1<<cnt;S++){
        for(int T=(S-1)&S;T;T=(T-1)&S)for(int i=1;i<=n*m;i++)
            if(f[i][T]+f[i][S-T]-a[i]<f[i][S]){
                f[i][S]=f[i][T]+f[i][S-T]-a[i];
                las[i][S]=make_pair(1,T);
            }
        for(int i=1;i<=n*m;i++)q.push(make_pair(f[i][S],i));
        dij(S);
    }
    for(int i=1;i<=n*m;i++)if(f[i][(1<<cnt)-1]<ans)ans=f[i][(1<<cnt)-1],ans1=i;
    printf("%d\n",ans);
    memset(vis,0,sizeof(vis));
    write(ans1,(1<<cnt)-1);
    for(int i=1;i<=n;i++,puts(""))for(int j=1;j<=m;j++){
        if(!a[id[i][j]])putchar('x');
        else if(vis[id[i][j]])putchar('o');
        else putchar('_');
    }
}