代码

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=15,K=(1<<12)+5,INF=0x3f3f3f3f;
int n,m,u,v,ww,ans=INF;
int f[K],d[N],g[N][N];
inline void dfs(int now)
{
    if(now==(1<<n)-1)
        return;
    for(int i=1;i<=n;i++)
    {
        if((now&(1<<i-1))==0)
            continue;
        for(int j=1;j<=n;j++)
        {
            if(g[i][j]==INF)
                continue;
            if(now&(1<<j-1))
                continue;
            d[j]=d[i]+1;
            if(f[now|(1<<j-1)]>f[now]+g[i][j]*d[j])
            {
                f[now|(1<<j-1)]=f[now]+g[i][j]*d[j];
                dfs(now|(1<<j-1));
            }
            d[j]=0;
        }
    }
}
int main()
{
    memset(g,0x3f,sizeof(g));
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&u,&v,&ww);
        g[u][v]=g[v][u]=min(g[u][v],ww);
    }
    for(int i=1;i<=n;i++)
    {
        memset(f,0x3f,sizeof(f));
        f[1<<i-1]=0;
        dfs(1<<i-1);
        ans=min(ans,f[(1<<n)-1]);
    }
    printf("%d\n",ans);
    return 0;
}

评测结果