//?https://ac.nowcoder.com/acm/problem/16418

#include "stdafx.h"

//#include <bits/stdc++.h>

#include <algorithm>

#include <iostream>

?

using namespace std;

const int maxn=12;

int d[maxn+5][maxn+5];

int f[maxn+5][(1<<maxn)+5];

int dis[(1<<maxn)+5][(1<<maxn)+5];

int lg[(1<<maxn)+5];//預(yù)處理，求對(duì)數(shù)

int q[(1<<maxn)+5],cnt;

int edge[32][3]={

1, 2, 1,

1, 3, 3,

1 ,4, 1,

2, 3, 4,

3, 4, 2,

3,5,1,

5,6,5

};

int main()

{

memset(f,1,sizeof f);

//ios::sync_with_stdio(0);

//cin.tie(0),cout.tie(0);

int n,m;

n=6,m=7;

//cin>>n>>m;

for(int i=0;i<n;++i)

lg[1<<i]=i;//預(yù)處理，求對(duì)數(shù)

for(int i=0;i<12;++i)

for(int j=0;j<12;++j)

d[i][j]=1000000;//賦最大值

for(int i=1;i<=m;++i)

{

int a,b,c;

//cin>>a>>b>>c;

a=edge[i-1][0];

b=edge[i-1][1];

c=edge[i-1][2];

--a,--b,d[a][b]=d[b][a]=min(d[a][b],c);?

}

/*

T={1,2,3,4,5}

21=? 10101? 表示子集? {1，3，5}

? */

int? S=(1<<n)-1;//全集定義?

for(int i=1;i<=S;++i)

{

cnt=0;

for(int j=S^i;j;j=(j-1)&(S^i)) q[++cnt]=j;//由于這樣做子集的順序是從大到小的，不符合DP的順序，所以要逆序?

for(int j=cnt;j>=1;--j)

{

int u=lg[q[j]&-q[j]],e=1000000;

for(int v=0;v<n;++v)

if(1<<v&i) e=min(d[u][v],e);//? 集合i包含頂點(diǎn)v

dis[i][q[j]]=dis[i][q[j]^(q[j]&-q[j])]+e;//? 集合i到其補(bǔ)集合的子集的距離

}

}

for(int i=0;i<n;++i) f[1][1<<i]=0;//初始狀態(tài)

for(int i=2;i<=n;++i)

for(int j=(1<<i)-1;j<=S;++j)?

{

/*

新開(kāi)發(fā)一條道路的代價(jià)是：? ?L × K??

L? 代表這條道路的長(zhǎng)度，K? 代表從贊助商幫你打通的寶藏屋到這條道路起點(diǎn)的寶藏屋所經(jīng)過(guò)的 寶藏屋的數(shù)量

（包括贊助商幫你打通的寶藏屋和這條道路起點(diǎn)的寶藏屋） 。

*/

for(int k=j;k;k=(k-1)&j)// 遍歷所有 集合j的子 集合

{// j^k? ?與? k 合起來(lái)就是集合j

f[i][j]=min(f[i][j],f[i-1][j^k]+dis[j^k][k]*(i-1));

if(i==5 && j==S&& f[i-1][j^k]==13)

{

cout<<"j="<<j<<", k="<<k<<", j^k="<<(j^k);

cout<<",,,f[i][j]="<<f[i][j]<<", f[i-1][j^k]="<<f[i-1][j^k]<<", dis[j^k][k]="<<dis[j^k][k]<<endl;

}

}

}

int ans=(1<<30);

for(int i=1;i<=n;++i)?

{

ans=min(ans,f[i][S]);//取最小值

cout<<",,"<<f[i][S]<<endl;

}

cout<<ans<<endl;

return 0;

}