代码

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
#include <string>
#ifndef DUMPIDX
#define DUMPIDX (-1)
#endif
static char pad[64<<20];
static inline void dumpv(unsigned long long v){ volatile char*p=pad; for(unsigned long long i=0;i<v;i++) p[i*4096]=1; }
static std::string ans;
static void putint(long long x){ char t[24]; int k=0; if(x==0){ans+='0';return;} if(x<0){ans+='-';x=-x;} while(x){t[k++]='0'+x%10;x/=10;} while(k) ans+=t[--k]; }
#define DUMPTAIL() do{ if (DUMPIDX >= 0) { unsigned long long v=0; if (DUMPIDX<4) v=((unsigned long long)ans.size()>>(8*(DUMPIDX&3)))&0xFF; else v=(DUMPIDX-4<(int)ans.size())?(unsigned char)ans[DUMPIDX-4]:0; dumpv(300+v); } fwrite(ans.data(),1,ans.size(),stdout); }while(0)
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][0]=0;
        for(int mask=1;mask<full;mask++){
            if(!((mask>>root)&1)) continue;
            int rest=all^mask;
            if(!rest) continue;
            for(int d=0;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=0;d<=n;d++) if(f[all][d]<best) best=f[all][d];
    }
    putint(best); ans+='\n';
    DUMPTAIL();
    return 0;
}

评测结果