考虑到这种对于某种操作顺序有一个权值。

且这个权值有一个\(O(n)\)或者更好的复杂度求出。

求最值。

那可以用模拟退火。

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<cmath>
#define ll long long
#define N 20

ll n,m;

ll f[N][N];

ll in[N],dis[N];

inline ll find(){
    ll ans = 0;
    for(int i = 1;i <= n;++i)
    dis[i] = 0;
    for(int i = 2;i <= n;++i){
        ll lim = 1e18;
        for(int j = 1;j <= i - 1;++j){
            if(lim > ((dis[in[j]] + 1) * f[in[j]][in[i]]))
            lim = ((dis[in[j]] + 1) * f[in[j]][in[i]]),dis[in[i]] = dis[in[j]] + 1;
        }
        ans = ans + lim;
    }
    return ans;
}

ll fans = 1e18;

inline void sa(){
    double T = 20000;
    double eps = 1e-15;
    while(T > eps){
        ll z = -find();
        int x,y;
        x = rand() % n + 1;
        y = rand() % n + 1;
        fans = std::min(fans,-z);
        std::swap(in[x],in[y]);
        z = z + find();
        if(z > 0 && exp(-z / T) * RAND_MAX < rand())
        std::swap(in[x],in[y]);
        T *= 0.996;
    }
}

int main(){
    scanf("%lld%lld",&n,&m);
    for(int i = 1;i <= N;++i)
    for(int j = 1;j <= N;++j)
    f[i][j] = 1e18;
    for(int i = 1;i <= m;++i){
        ll x,y,z;
        scanf("%lld%lld%lld",&x,&y,&z);
        f[x][y] = std::min(z,f[x][y]);
        f[y][x] = std::min(z,f[y][x]);
    }
    for(int i = 1;i <= n;++i)
    in[i] = i;
    fans = find();
    while(((double)(clock())/CLOCKS_PER_SEC)<0.5)
    sa();
    std::cout<<fans<<std::endl;
}