题意就不多说了
显而易见，所求的定为一棵树
首先，这个题可以用连通性状态压缩动态规划来写，但感觉思路清晰，实现复杂（较于第二种方法），所以果断写了树结构状态压缩dp
假设f[i][j][s]为已知景点连通性为s集合，其中每一二进制位1表示已连接，0表示未连接
转移显然有两种（以下省略取最小的min）
第一：将两个同根树合并，f[i][j][s]=f[i][j][t]+f[i][j][s^t]（t belongs to s）
第二：从（i，j）移向四周即加入（i’，j‘）并将根节点指向（i'，j'）即f[i'][j'][s'=sU(i',j')]=f[i][j][s]+cost[i'][j']
其中对于s'=sU(i',j')的意思就是如果(i',j')是景点则加入s中，否则s不变
枚举每个s，保证s的子集已计算后，先将每个f[i][j][s]按第一个转移更新
对于第二个转移，由于转移可以从（i，j）到（i'，j'），也可从（i’，j'）到（i，j），将其看做多源最短路问题，（i，j）表示一个点，f[i][j][s]表示当前最短距离，Djstra或SPFA皆可
然后在第二个转移中特判s变化的转移，因为s'!=s时，转移是单向的
以上是正解
但是，有一种坑爹dp也是正确的
f[i][j][s]中s表示已知哪些景点必联通的最小代价，s中1表示当前景点已知连通，0表示当前节点为混乱状态，即可能联通也可能不连通
转移同上，但第二个转移时s恒不变，即不管（i'，j'）是否为景点，就不要特判了
个人想了一下第二种树状压dp之所以正确的原因：
首先由于ans的方案一定为树，那么若不特判，也可以保证是棵树，经过景点时可以认为是代价为0的节点，否则如果特判了，由于s不变，你必须要绕一个大圈才回到某节点，往后更新时就会有环，但你无法删除多余的环，反倒使ans变劣了
读者可以比较一下两种dp代码，几乎一模一样
PS：由于偷懒，我木有输出方案
第一种正解的：
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
int mm[15][15],f[15][15][2056],a[15][15],n=0,m=0,nn=0,ans=0;
bool v[15][15];
int stai[3000000],staj[3000000];
bool downdate(int &a,int b)
{
if (a>b)
{
a=b;
return 1;
}
return 0;
}
int main()
{
freopen("trip.in","r",stdin);
freopen("trip.out","w",stdout);
scanf("%d%d",&n,&m);
int i=0,j=0;
memset(f,60,sizeof(f));
int oo=f[0][0][0]-1;
for (i=1;i<=n;i++)
for (j=1;j<=m;j++)
{
scanf("%d",&a[i][j]);
if (a[i][j]==0)
{
++nn;
mm[i][j]=1<<(nn-1);
f[i][j][mm[i][j]]=0;
}
else
f[i][j][0]=a[i][j];
}
int state=0,t=0,top=0,tail=0,xi=0,xj=0;
bool tmp=0;
for (state=0;state<=(1<<nn)-1;state++)
{
top=tail=0;
memset(v,0,sizeof(v));
for (i=1;i<=n;i++)
for (j=1;j<=m;j++)
{
for (t=state&(state-1);t;t=(t-1)&state)
tmp=downdate(f[i][j][state],f[i][j][t]+f[i][j][state^t]-a[i][j]);
if (f[i][j][state]>=oo) continue;
stai[++tail]=i;
staj[tail]=j;
v[i][j]=1;
}//第一种转移，以下为第二种
while (top<tail)
{
xi=stai[++top];
xj=staj[top];
if (xi>1)
{
if ((mm[xi-1][xj]==0)||(mm[xi-1][xj]&state))
{
if (downdate(f[xi-1][xj][state],f[xi][xj][state]+a[xi-1][xj]))
if (!v[xi-1][xj])
{
stai[++tail]=xi-1;
staj[tail]=xj;
v[xi-1][xj]=1;
}
}
else
{
tmp=downdate(f[xi-1][xj][state|mm[xi-1][xj]],f[xi][xj][state]);
tmp=downdate(f[xi][xj][state|mm[xi-1][xj]],f[xi][xj][state]);
}//s改变时的特判,下同
}
if (xj>1)
{
if ((mm[xi][xj-1]==0)||(mm[xi][xj-1]&state))
{
if (downdate(f[xi][xj-1][state],f[xi][xj][state]+a[xi][xj-1]))
if (!v[xi][xj-1])
{
stai[++tail]=xi;
staj[tail]=xj-1;
v[xi][xj-1]=1;
}
}
else
{
tmp=downdate(f[xi][xj-1][state|mm[xi][xj-1]],f[xi][xj][state]);
tmp=downdate(f[xi][xj][state|mm[xi][xj-1]],f[xi][xj][state]);
}
}
if (xi<n)
{
if ((mm[xi+1][xj]==0)||(mm[xi+1][xj]&state))
{
if (downdate(f[xi+1][xj][state],f[xi][xj][state]+a[xi+1][xj]))
if (!v[xi+1][xj])
{
stai[++tail]=xi+1;
staj[tail]=xj;
v[xi+1][xj]=1;
}
}
else
{
tmp=downdate(f[xi+1][xj][state|mm[xi+1][xj]],f[xi][xj][state]);
tmp=downdate(f[xi][xj][state|mm[xi+1][xj]],f[xi][xj][state]);
}
}
if (xj<m)
{
if ((mm[xi][xj+1]==0)||(mm[xi][xj+1]&state))
{
if (downdate(f[xi][xj+1][state],f[xi][xj][state]+a[xi][xj+1]))
if (!v[xi][xj+1])
{
stai[++tail]=xi;
staj[tail]=xj+1;
v[xi][xj+1]=1;
}
}
else
{
tmp=downdate(f[xi][xj+1][state|mm[xi][xj+1]],f[xi][xj][state]);
tmp=downdate(f[xi][xj][state|mm[xi][xj+1]],f[xi][xj][state]);
}
}
v[xi][xj]=0;
}
}
ans=oo;
for (i=1;i<=n;i++)
for (j=1;j<=m;j++)
tmp=downdate(ans,f[i][j][(1<<nn)-1]);
printf("%d",ans);
return 0;
}
第二种坑爹dp：（真的只改了一下）
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
int mm[15][15],f[15][15][2056],a[15][15],n=0,m=0,nn=0,ans=0;
bool v[15][15];
int stai[3000000],staj[3000000];
bool downdate(int &a,int b)
{
if (a>b)
{
a=b;
return 1;
}
return 0;
}
int main()
{
freopen("trip.in","r",stdin);
freopen("trip.out","w",stdout);
scanf("%d%d",&n,&m);
int i=0,j=0;
memset(f,60,sizeof(f));
int oo=f[0][0][0]-1;
for (i=1;i<=n;i++)
for (j=1;j<=m;j++)
{
scanf("%d",&a[i][j]);
if (a[i][j]==0)
{
++nn;
mm[i][j]=1<<(nn-1);
f[i][j][mm[i][j]]=0;
}
else
f[i][j][0]=a[i][j];
}
int state=0,t=0,top=0,tail=0,xi=0,xj=0;
bool tmp=0;
for (state=0;state<=(1<<nn)-1;state++)
{
top=tail=0;
memset(v,0,sizeof(v));
for (i=1;i<=n;i++)
for (j=1;j<=m;j++)
{
for (t=state&(state-1);t;t=(t-1)&state)
tmp=downdate(f[i][j][state],f[i][j][t]+f[i][j][state^t]-a[i][j]);
if (f[i][j][state]>=oo) continue;
stai[++tail]=i;
staj[tail]=j;
v[i][j]=1;
}
while (top<tail)//第二种，木有特判了，有木有有木有
{
xi=stai[++top];
xj=staj[top];
if (xi>1)
{
if (downdate(f[xi-1][xj][state],f[xi][xj][state]+a[xi-1][xj]))
if (!v[xi-1][xj])
{
stai[++tail]=xi-1;
staj[tail]=xj;
v[xi-1][xj]=1;
}
}
if (xj>1)
{
if (downdate(f[xi][xj-1][state],f[xi][xj][state]+a[xi][xj-1]))
if (!v[xi][xj-1])
{
stai[++tail]=xi;
staj[tail]=xj-1;
v[xi][xj-1]=1;
}
}
if (xi<n)
{
if (downdate(f[xi+1][xj][state],f[xi][xj][state]+a[xi+1][xj]))
if (!v[xi+1][xj])
{
stai[++tail]=xi+1;
staj[tail]=xj;
v[xi+1][xj]=1;
}
}
if (xj<m)
{
if (downdate(f[xi][xj+1][state],f[xi][xj][state]+a[xi][xj+1]))
if (!v[xi][xj+1])
{
stai[++tail]=xi;
staj[tail]=xj+1;
v[xi][xj+1]=1;
}
}
v[xi][xj]=0;
}
}
ans=oo;
for (i=1;i<=n;i++)
for (j=1;j<=m;j++)
tmp=downdate(ans,f[i][j][(1<<nn)-1]);
printf("%d",ans);
return 0;
}