代码

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
const int INF=0x3f3f3f3f;
static int g[13][13];
static int mnw[1<<12][12];
static int f[1<<12][13];
int main(){
    int n,m; if(scanf("%d %d",&n,&m)!=2) return 0;
    memset(g,0x3f,sizeof g);
    for(int i=0;i<m;i++){int a,b,w;scanf("%d %d %d",&a,&b,&w);--a;--b; if(w<g[a][b]){g[a][b]=w;g[b][a]=w;}}
    int full=1<<n, all=full-1;
    for(int v=0;v<n;v++) mnw[0][v]=INF;
    for(int mask=1;mask<full;mask++){
        int lb=__builtin_ctz(mask);
        for(int v=0;v<n;v++){ int a=mnw[mask^(1<<lb)][v], b=g[v][lb]; mnw[mask][v]= a<b?a:b; }
    }
    int best=INF;
    for(int root=0;root<n;root++){
        for(int mask=0;mask<full;mask++) for(int d=0;d<=n;d++) f[mask][d]=INF;
        f[1<<root][1]=0;
        for(int mask=1;mask<full;mask++){
            if(!((mask>>root)&1)) continue;
            int rest=all^mask;
            if(!rest) continue;
            for(int d=1;d<n;d++){
                int base=f[mask][d];
                if(base>=INF) continue;
                for(int T=rest;T;T=(T-1)&rest){
                    long long c=0; bool ok=true;
                    int tt=T;
                    while(tt){ int v=__builtin_ctz(tt); tt&=tt-1; int w=mnw[mask][v]; if(w>=INF){ok=false;break;} c += (long long)w*(d+1); }
                    if(!ok) continue;
                    int nv=base+(int)c;
                    if(nv<f[mask|T][d+1]) f[mask|T][d+1]=nv;
                }
            }
        }
        for(int d=1;d<=n;d++) if(f[all][d]<best) best=f[all][d];
    }
    printf("%d\n",best);
    return 0;
}

评测结果