代码

#include <stdio.h>
#include <string.h>
#define INF 0x3f3f3f3f
int g[13][13]; int n, m;
int dp[1<<12][13];
int main(){
    scanf("%d%d", &n, &m);
    memset(g, 0x3f, sizeof(g));
    for(int i=0;i<m;i++){ int u,v,w; scanf("%d%d%d",&u,&v,&w); u--;v--; if(w<g[u][v]) g[u][v]=g[v][u]=w; }
    int full = (1<<n)-1; int ans = INF;
    for(int root=0; root<n; root++){
        memset(dp, 0x3f, sizeof(dp));
        dp[1<<root][0] = 0;
        for(int mask=1; mask<=full; mask++){
            for(int d=0; d<n; d++){
                if(dp[mask][d] >= INF) continue;
                int rest = full ^ mask;
                for(int sub=rest; sub; sub=(sub-1)&rest){
                    int c=0, ok=1, v;
                    for(v=0; v<n; v++) if(sub>>v & 1){
                        int mn=INF, u;
                        for(u=0; u<n; u++) if((mask>>u & 1) && g[u][v] < mn) mn=g[u][v];
                        if(mn>=INF){ ok=0; break; }
                        c += mn;
                    }
                    if(!ok) continue;
                    int nm = mask|sub; int nc = dp[mask][d] + c*(d+1);
                    if(nc < dp[nm][d+1]) dp[nm][d+1] = nc;
                }
            }
        }
        int d; for(d=0; d<n; d++) if(dp[full][d] < ans) ans = dp[full][d];
    }
    printf("%d\n", ans);
    return 0;
}

评测结果