spfa+dfs+bfs

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
int ans,n,m,a[20][20],vis[20],b[20],c[20],d[20][20],anss=0x3f3f3f3f;
void bfs(int k){
    queue<int>q;
    q.push(k);
    c[k]=1;
    while(!q.empty()){
        int p=q.front();q.pop();
        for(int i=1;i<=n;i++)
            if(c[i]==-1&&a[i][p]!=-1) {
                c[i]=c[p]+1;
                q.push(i);
            }
    }
}
void dfs(int k,int s){
    if(s>=ans||s>=anss) return;
    if(k==n) {ans=s;return;}
    for(int i=1;i<=n;i++){
        if(!vis[i]){
            int h=0x3f3f3f3f;
            for(int j=1;j<=n;j++)
                if(a[i][j]!=-1&&vis[j]&&c[j]!=-1)
                    h=min(h,c[j]*a[j][i]);
            vis[i]=1;
            dfs(k+1,s+h);
            vis[i]=0;
        }
    }
}
int main(){
    scanf("%d%d",&n,&m);
    memset(a,0x3f,sizeof(a));
    for(int i=1;i<=m;i++){
        int x,y,v;
        scanf("%d%d%d",&x,&y,&v);
        a[x][y]=min(a[x][y],v);
        a[y][x]=a[x][y];
    }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            if(a[i][j]==0x3f3f3f3f) a[i][j]=-1;
    for(int i=1;i<=n;i++) {
        memset(vis,0,sizeof(vis));
        memset(b,0,sizeof(b));
        memset(c,-1,sizeof(c));
        memset(d,0,sizeof(d));
        bfs(i);
        ans=0x3f3f3f3f;
        vis[i]=1;
        dfs(1,0);
        anss=min(ans,anss);
    }
    printf("%d",anss);
    return 0;
}