题目:https://www.luogu.org/problemnew/show/P3959
搜索;
不是记忆化,而是剪枝;
邻接矩阵存边即可,因为显然没有那么多边。
代码如下:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
ll const inf=0x3f3f3f3f3f3f3f3f;
int n,m,S,sid[][];
ll s[<<],ans,dis[];
ll dfs(int p,ll w)
{
if(w>=ans)return inf;
if(p==S)return w;
// if(s[p])return s[p];//错误记忆化
s[p]=min(s[p],w);//
ll ret=inf;
for(int x=;x<=n;x++)
{
if((p&(<<(x-)))==)continue;
for(int u=;u<=n;u++) if(sid[x][u]!=inf&&((<<(u-))&p)==)
{
int np=(p|(<<(u-)));
if(s[np]<=w+sid[x][u]*(dis[x]+))continue;//最优性剪枝
dis[u]=dis[x]+;
ret=min(ret,dfs(np,w+sid[x][u]*dis[u]));
dis[u]=;
}
}
return ret;
}
int main()
{
scanf("%d%d",&n,&m);
memset(sid,0x3f,sizeof sid);
for(int i=,x,y,z;i<=m;i++)
{
scanf("%d%d%d",&x,&y,&z);
sid[x][y]=min(sid[x][y],z);
sid[y][x]=sid[x][y];
}
ans=inf; S=(<<n)-;
for(int i=;i<=n;i++)
{
memset(s,0x3f,sizeof s);
ans=min(ans,dfs(<<(i-),));
}
printf("%lld\n",ans);
return ;
}