引题
状压dp，全称为状态压缩动态规划，是一种利用二进制的数来表示状态的动态规划
我们经常用二进制中某一位的1表示选取这一位表示的状态，用0表示相反的意义
例如：现在有一张有(n)个节点的图，我们需要找到经过某些特定点的最短路
假设(n=8)，那么二进制数10010011的意义如下
| 节点编号 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|
| 二进制数 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | 1 |
| 是否有当前节点 | Y | N | N | Y | N | N | Y | Y |
这样我们就可以用(2^n-1)个二进制数来表示所有状态
不过我们知道形如(2^n)的数在(n)较大时会变得很大，这也决定了状压题的一个显著特点——(n)值较小
同时为了得到更优秀的时间，我们经常减去许多不必要的状态
这一步我们通过位运算实现
位运算
在得到状态之后，我们会对这些状态进行一些访问与操作，这就要用到位运算
常见的位运算有如下集中
1、‘&’ 符号，(x&y)表示x与y的和运算
2、‘|’符号，(x|y)表示x与y的或运算
3、'^'符号，表示x与y的异或运算（相同为0，不相同为1）
4、<<与>>，<<是左移，如(x<<2)表示将x的二进制下的每一位向右移动两位（新出现的为用0补充）
同样的，>>是右移，(x>>1)表示去掉x的二进制表示下的最后一位
5、~符号，表示二进制取反（顾名思义），不过要尤其注意二进制下对负数的存储方式，不过好像用的不多
用上述运算可以进行一些虽然基础但是十分重要的运算
1、判断二进制数x的第i位是否为1
方法：(if ((1<<(i-1))&x))，我们用(1<<(i-1))构造出了一个只有第(i)位上是1的数，然后直接与x进行运算即可
2、将一个二进制数x的第i为改成1
方法：(x=x|(1<<(i-1)))，与1大体相同，不过是将&改成了|
3、枚举子集 (x&(x-1))
这一步乍一看是将x的最右边一位的1去掉了，但是仔细想想，由于在x中不是1的位上，得到的新数中相对应的位也不可能是1，x中是1的位上，得到的新数也有可能不是1，所以我们可以用这一种方法来枚举x表示的状态中的子集
4、去掉二进制数x中第i为的1（保证第i位上有1）
方法：x^(1<<(i-1)) 与上面类似
例题
1、poj3311 Hie with the Pie
| Time Limit: 2000MS | | Memory Limit: 65536K |
| ---------------------------- | | ------------------------ |
| Total Submissions: 10034 | | Accepted: 5416 |
Description
The Pizazz Pizzeria prides itself in delivering pizzas to its customers as fast as possible. Unfortunately, due to cutbacks, they can afford to hire only one driver to do the deliveries. He will wait for 1 or more (up to 10) orders to be processed before he starts any deliveries. Needless to say, he would like to take the shortest route in delivering these goodies and returning to the pizzeria, even if it means passing the same location(s) or the pizzeria more than once on the way. He has commissioned you to write a program to help him.
Input
Input will consist of multiple test cases. The first line will contain a single integer n indicating the number of orders to deliver, where 1 ≤ n ≤ 10. After this will be n + 1 lines each containing n + 1 integers indicating the times to travel between the pizzeria (numbered 0) and the n locations (numbers 1 to n). The jth value on the ith line indicates the time to go directly from location i to location j without visiting any other locations along the way. Note that there may be quicker ways to go from i to j via other locations, due to different speed limits, traffic lights, etc. Also, the time values may not be symmetric, i.e., the time to go directly from location i to j may not be the same as the time to go directly from location j to i. An input value of n = 0 will terminate input.
Output
For each test case, you should output a single number indicating the minimum time to deliver all of the pizzas and return to the pizzeria.
Sample Input
3
0 1 10 10
1 0 1 2
10 1 0 10
10 2 10 0
0
Sample Output
8
Source
East Central North America 2006
题意：一个人要送n份货，给出一个矩阵表示一张图(n<=10)，表示任意两个点间的直接路径的时间，求从起点0送完这n份货（到达指定的n个地点）再回到起点0的最短时间
题解：看到这题n这么小就要考虑状压了
由于要求回到起点的最小路径，我们可以考虑将路径拆成两部分——从起点到达某个点，再从那个点回到起点，后面那一部分只有一条路径
很明显会首先用floyd求出所有点之间的最短路
接下来就是设计状态，我们用(dp[i][j])表示在(i)的状态下（即已经经过了哪些点）且终点为(j)时所花的最短时间。很明显我们对(i)进行了状压
1）如果(i)中只有1位且为(j)，那么直接加上从起点到(j)的时间
2）如果(i)中不只有(j)这一位，那我们要考虑从中间某一点(k)作为中继点进行转移
转移方程(dp[i][j]=min(dp[i][j],dp[i ext^(1<<(j-1))][k]+dis[j][k]))
最后按照上面的统计答案即可
#include<iostream>
#include<string.h>
#include<string>
#include<stdio.h>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
using namespace std;
int dp[10100][12],n,sq[12][12];
int read()
{
int x=0,f=1;char ch=getchar();
while ((ch<'0') || (ch>'9')) {if (ch=='-') f=-1;ch=getchar();}
while ((ch>='0') && (ch<='9')) {x=x*10+(ch-'0');ch=getchar();}
return x*f;
}
int main()
{
while ((scanf("%d",&n)!=EOF) && (n))
{
int i,j,k;
for (i=0;i<=n;i++)
for (j=0;j<=n;j++) sq[i][j]=read();
for (k=0;k<=n;k++)
{
for (i=0;i<=n;i++)
{
for (j=0;j<=n;j++)
sq[i][j]=min(sq[i][j],sq[i][k]+sq[k][j]);
}
}
for (i=0;i<(1<<n);i++)
{
for (j=1;j<=n;j++)
{
if (i==(1<<(j-1))) dp[i][j]=sq[0][j];
else
{
dp[i][j]=1e9+7;
for (k=1;k<=n;k++)
if ((j!=k) && (i&(1<<(j-1))))
dp[i][j]=min(dp[i][j],dp[i^(1<<(j-1))][k]+sq[k][j]);
}
}
}
int ans=1e9+7,all=(1<<n)-1;
for (i=1;i<=n;i++) ans=min(ans,dp[all][i]+sq[i][0]);
printf("%d
",ans);
}
return 0;
}
/*
3
0 1 10 10
1 0 1 2
10 1 0 10
10 2 10 0
0
*/
2、[USACO08NOV]Mixed Up Cows
题目描述
Each of Farmer John's N (4 <= N <= 16) cows has a unique serial number S_i (1 <= S_i <= 25,000). The cows are so proud of it that each one now wears her number in a gangsta manner engraved in large letters on a gold plate hung around her ample bovine neck.
Gangsta cows are rebellious and line up to be milked in an order called 'Mixed Up'. A cow order is 'Mixed Up' if the sequence of serial numbers formed by their milking line is such that the serial numbers of every pair of consecutive cows in line differs by more than K (1 <= K <= 3400). For example, if N = 6 and K = 1 then 1, 3, 5, 2, 6, 4 is a 'Mixed Up' lineup but 1, 3, 6, 5, 2, 4 is not (since the consecutive numbers 5 and 6 differ by 1).
How many different ways can N cows be Mixed Up?
For your first 10 submissions, you will be provided with the results of running your program on a part of the actual test data.
约翰家有N头奶牛，第i头奶牛的编号是Si，每头奶牛的编号都是唯一的。这些奶牛最近 在闹脾气，为表达不满的情绪，她们在挤奶的时候一定要排成混乱的队伍。在一只混乱的队 伍中，相邻奶牛的编号之差均超过K。比如当K = 1时，1, 3, 5, 2, 6, 4就是一支混乱的队伍， 而1, 3, 6, 5, 2, 4不是，因为6和5只差1。请数一数，有多少种队形是混乱的呢？
输入输出格式
输入格式：
* Line 1: Two space-separated integers: N and K
* Lines 2..N+1: Line i+1 contains a single integer that is the serial number of cow i: S_i
输出格式：
* Line 1: A single integer that is the number of ways that N cows can be 'Mixed Up'. The answer is guaranteed to fit in a 64 bit integer.
输入输出样例
输入样例#1：
4 1
3
4
2
1
输出样例#1：
2
说明
The 2 possible Mixed Up arrangements are:
3 1 4 2
2 4 1 3
这一题比上面的那一题还好做一些
一看到(4leq n leq 16)就知道我们要对它进行状压
我们记(dp[i][j])表示当前状态为(i)，且最后一个被加入该状态的是(j)
那么转移方程是很显然的，如果(j)在状态(i)中且(k)不在，则(dp[(1<<(k-1))|i][k]+=dp[i][j])
最后答案就是(sum^n_{i=1} {dp[(1<<n)-1][i]})
#include<iostream>
#include<string.h>
#include<string>
#include<stdio.h>
#include<algorithm>
#include<math.h>
#include<vector>
#include<queue>
#include<map>
using namespace std;
long long dp[100100][18];
int n,high[18],cha;
int read()
{
int x=0,f=1;char ch=getchar();
while ((ch<'0') || (ch>'9')) {if (ch=='-') f=-1;ch=getchar();}
while ((ch>='0') && (ch<='9')) {x=x*10+(ch-'0');ch=getchar();}
return x*f;
}
int main()
{
memset(dp,0,sizeof(dp));
n=read();cha=read();
int i,j,k;
for (i=1;i<=n;i++) {high[i]=read();dp[1<<(i-1)][i]=1;}
int all=(1<<n)-1;
//cout << all << endl;
for (i=1;i<=all;i++)
{
for (j=1;j<=n;j++)
{
for (k=1;k<=n;k++)
{
if ((abs(high[j]-high[k])<=cha) && ((1<<(j-1))&i) && (((1<<(k-1))&i)==0))
dp[(1<<(k-1))|i][k]+=dp[i][j];
}
}
}
long long ans=0;
for (i=1;i<=n;i++) ans+=dp[all][i];
printf("%lld",ans);
return 0;
}
/*
4 1
3
4
2
1
*/
3、[USACO06NOV]Corn Fields
题目描述
Farmer John has purchased a lush new rectangular pasture composed of M by N (1 ≤ M ≤ 12; 1 ≤ N ≤ 12) square parcels. He wants to grow some yummy corn for the cows on a number of squares. Regrettably, some of the squares are infertile and can't be planted. Canny FJ knows that the cows dislike eating close to each other, so when choosing which squares to plant, he avoids choosing squares that are adjacent; no two chosen squares share an edge. He has not yet made the final choice as to which squares to plant.
Being a very open-minded man, Farmer John wants to consider all possible options for how to choose the squares for planting. He is so open-minded that he considers choosing no squares as a valid option! Please help Farmer John determine the number of ways he can choose the squares to plant.
农场主John新买了一块长方形的新牧场，这块牧场被划分成M行N列(1 ≤ M ≤ 12; 1 ≤ N ≤ 12)，每一格都是一块正方形的土地。John打算在牧场上的某几格里种上美味的草，供他的奶牛们享用。
遗憾的是，有些土地相当贫瘠，不能用来种草。并且，奶牛们喜欢独占一块草地的感觉，于是John不会选择两块相邻的土地，也就是说，没有哪两块草地有公共边。
John想知道，如果不考虑草地的总块数，那么，一共有多少种种植方案可供他选择？（当然，把新牧场完全荒废也是一种方案）
输入输出格式
输入格式：
第一行：两个整数M和N，用空格隔开。
第2到第M+1行：每行包含N个用空格隔开的整数，描述了每块土地的状态。第i+1行描述了第i行的土地，所有整数均为0或1，是1的话，表示这块土地足够肥沃，0则表示这块土地不适合种草。
输出格式：
一个整数，即牧场分配总方案数除以100,000,000的余数。
输入输出样例
输入样例#1：
2 3
1 1 1
0 1 0
输出样例#1：
9
我们显然发现：每一行之间是相对独立的。即：这一行的状态（是否合法）不会影响到下一行是否合法
有了这个想法我们就可以考虑将每一行的田是否可用进行状压，同时预处理出所有合法的情况
那么一个重要的问题是：如何判断当前状态（记为(now)为合法的状态）
我们知道，一个状态合法仅当该状态中没有相邻的1出现
即：将(now)左移或右移一位，与原来值的&为0
写作：(((now ext&(now>>1)) ext& ext&(now ext&(now<<1))))
那么接下来就比较简单了
记(dp[i][j])为走到了第(i)行，且当前的这一行选取的状态是(j)时的方案数
保证(j)的合法性自不必说（本身合法且可以存在于这一行）
我们枚举上一行的状态(k)，当这两行的状态合法时（(j ext&k==0)）我们进行转移（(dp[i][j]+=dp[i-1][k])）
最后答案是(sum^{all}_{i=0} dp[m][i])
#include<iostream>
#include<string.h>
#include<string>
#include<stdio.h>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
using namespace std;
const int maxd=1e9;
int sq[13][13],n,m,dp[13][10100],maxs,hang[13];
bool sit[10100];
int read()
{
int x=0,f=1;char ch=getchar();
while ((ch<'0') || (ch>'9')) {if (ch=='-') f=-1;ch=getchar();}
while ((ch>='0') && (ch<='9')) {x=x*10+(ch-'0');ch=getchar();}
return x*f;
}
int main()
{
m=read();n=read();
int i,j,k;
for (i=1;i<=m;i++)
{
for (j=1;j<=n;j++)
sq[i][j]=read();
}
memset(hang,0,sizeof(hang));
maxs=1<<n;
for (i=1;i<=m;i++)
for (j=1;j<=n;j++)
hang[i]=(hang[i]<<1)+sq[i][j];
for (i=0;i<maxs;i++)
sit[i]=(((i&(i>>1))==0) && ((i&(i<<1))==0));
//for (i=0;i<maxs;i++) cout << sit[i] << " ";cout << endl;
memset(dp,0,sizeof(dp));dp[0][0]=1;
for (i=1;i<=m;i++)
{
for (j=0;j<maxs;j++)
{
if ((sit[j]) && ((hang[i]&j)==j))
{
for (k=0;k<maxs;k++)
if (!(k&j)) dp[i][j]=(dp[i][j]+dp[i-1][k])%maxd;
}
}
}
int ans=0;
for (i=0;i<maxs;i++) ans=(ans+dp[m][i])%maxd;
printf("%d",ans);
return 0;
}
4、Square Subsets
C. Square Subsets
time limit per test
4 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
Petya was late for the lesson too. The teacher gave him an additional task. For some array a Petya should find the number of different ways to select non-empty subset of elements from it in such a way that their product is equal to a square of some integer.
Two ways are considered different if sets of indexes of elements chosen by these ways are different.
Since the answer can be very large, you should find the answer modulo 109 + 7.
Input
First line contains one integer n (1 ≤ n ≤ 105) — the number of elements in the array.
Second line contains n integers a**i (1 ≤ a**i ≤ 70) — the elements of the array.
Output
Print one integer — the number of different ways to choose some elements so that their product is a square of a certain integer modulo 109 + 7.
Examples
Input
Copy
4
1 1 1 1
Output
Copy
15
Input
Copy
4
2 2 2 2
Output
Copy
7
Input
5
1 2 4 5 8
Output
7
Note
In first sample product of elements chosen by any way is 1 and 1 = 12. So the answer is 24 - 1 = 15.
In second sample there are six different ways to choose elements so that their product is 4, and only one way so that their product is 16. So the answer is 6 + 1 = 7.
题意：给定n个数(a_i)，从中选一些数求有多少个集合使得集合中的数乘积为完全平方数
zzr的博客怎么可以没有cf的题呢
本题的突破口在于(1leq a_i leq 70)，很明显会对它进行状压
但是你解题的策略会直接决定时间复杂度与空间复杂度
普通的状压肯定是不可以的，我们需要考虑一些有趣的性质
如果一个数是完全平方数，那么它的质因数分解中每个质因子的次方数都是偶数
而我们又注意到不大于70的质因数只有19个
将两者结合起来，我们可以记录状态(i)为二进制表示下(i)的第(j)位表示第(j)个质数在某个数质因数分解中出现的奇偶性
同时记(dp[i][j])表示当前选取数(i)，得到的乘积质因数分解可以被表示为(j)的方案数
那么对于每一个序列中出现的数(x)，记(sit[x])为它的质因数分解情况
我们先将所有的(x)丢到一个桶中，记(cnt[i])为数(i)在序列中的出现次数
那么很容易写出dp式子：
(dp[i][j]=sum^{all}_{j=0}dp[i-1][j]*2^{cnt_i-1})
(dp[i][j ext^sit[i]]=sum^{all}_{j=0}dp[i-1][j]*2^{cnt_i-1})
解释，对于已经有的一个乘积，我们将它乘上(i^k(k in Z))，如果(k)是偶数，那么它对原来的质因数分解不会产生新的影响，
反之，如果(k)是一个奇数，那么它与当前状态拥有相同的奇数质因子的部分将变成有偶数个，它所拥有的奇数质因子会使新的状态带上新的奇数质因子，所以我们进行一个异或运算即可。
如果数(i)并未出现，那么(dp[i][j])直接从(dp[i-1][j])继承即可，最终答案是(dp[70][0]-1)(所有的质因子都是偶数个，但是要去掉所有数都不选的情况)
时间复杂度约为(O(70*2^{19}))
然后就是空间问题
我们开的(dp)数组的大小：(70*2^{19}*4approx 1.4*10^8B=140MB)，刚好卡过去
但是这样就不能开long long，否则空间就是(280MB)，直接MLE
解决方法要么是在变量名前开(long long)，要么就是使用滚动数组
下面的程序采用了第一种方法
#include<iostream>
#include<string.h>
#include<string>
#include<stdio.h>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
using namespace std;
const int maxd=1e9+7,pri[]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67};
int n,cnt[71],sit[71],dp[71][1<<19],powe[100500];
int read()
{
int x=0,f=1;char ch=getchar();
while ((ch<'0') || (ch>'9')) {if (ch=='-') f=-1;ch=getchar();}
while ((ch>='0') && (ch<='9')) {x=x*10+(ch-'0');ch=getchar();}
return x*f;
}
void init()
{
int i,j;
memset(sit,0,sizeof(sit));
for (i=2;i<=70;i++)
{
int x=i;
for (j=0;j<19;j++)
{
while (x%pri[j]==0) {x/=pri[j];sit[i]^=(1<<j);}
}
}
}
int main()
{
n=read();init();
int i,j,all=(1<<19);
memset(cnt,0,sizeof(cnt));
for (i=1;i<=n;i++) {int x=read();cnt[x]++;}
powe[0]=1;
for (i=1;i<=n;i++) powe[i]=(powe[i-1]*2)%maxd;
memset(dp,0,sizeof(dp));dp[0][0]=1;
for (i=1;i<=70;i++)
{
if (cnt[i])
{
//cout << i << " " << cnt[i] << endl;
for (j=0;j<all;j++)
{
dp[i][j]=((long long)dp[i][j]+(long long)dp[i-1][j]*powe[cnt[i]-1])%maxd;
dp[i][j^sit[i]]=((long long)dp[i][j^sit[i]]+(long long)dp[i-1][j]*powe[cnt[i]-1])%maxd;
}
}
else
{
for (j=0;j<all;j++) dp[i][j]=dp[i-1][j];
}
}
printf("%d",(dp[70][0]-1+maxd)%maxd);
return 0;
}
5、宝藏NOIp2017D2T2
题目描述
参与考古挖掘的小明得到了一份藏宝图，藏宝图上标出了 nnn 个深埋在地下的宝藏屋， 也给出了这 nnn 个宝藏屋之间可供开发的m mm 条道路和它们的长度。
小明决心亲自前往挖掘所有宝藏屋中的宝藏。但是，每个宝藏屋距离地面都很远， 也就是说，从地面打通一条到某个宝藏屋的道路是很困难的，而开发宝藏屋之间的道路 则相对容易很多。
小明的决心感动了考古挖掘的赞助商，赞助商决定免费赞助他打通一条从地面到某 个宝藏屋的通道，通往哪个宝藏屋则由小明来决定。
在此基础上，小明还需要考虑如何开凿宝藏屋之间的道路。已经开凿出的道路可以 任意通行不消耗代价。每开凿出一条新道路，小明就会与考古队一起挖掘出由该条道路 所能到达的宝藏屋的宝藏。另外，小明不想开发无用道路，即两个已经被挖掘过的宝藏 屋之间的道路无需再开发。
新开发一条道路的代价是：
L×K
L代表这条道路的长度，K代表从赞助商帮你打通的宝藏屋到这条道路起点的宝藏屋所经过的 宝藏屋的数量（包括赞助商帮你打通的宝藏屋和这条道路起点的宝藏屋） 。
请你编写程序为小明选定由赞助商打通的宝藏屋和之后开凿的道路，使得工程总代 价最小，并输出这个最小值。
输入输出格式
输入格式：
第一行两个用空格分离的正整数 n,mn,mn,m，代表宝藏屋的个数和道路数。
接下来 mmm 行，每行三个用空格分离的正整数，分别是由一条道路连接的两个宝藏 屋的编号（编号为 1−n1-n1−n），和这条道路的长度 vvv。
输出格式：
一个正整数，表示最小的总代价。
输入输出样例
输入样例#1：
复制
4 5
1 2 1
1 3 3
1 4 1
2 3 4
3 4 1
输出样例#1：
复制
4
输入样例#2：
复制
4 5
1 2 1
1 3 3
1 4 1
2 3 4
3 4 2
输出样例#2：
复制
5
说明
【样例解释1】
小明选定让赞助商打通了1 11 号宝藏屋。小明开发了道路 1→21 o 21→2，挖掘了 222 号宝 藏。开发了道路 1→41 o 41→4，挖掘了 444 号宝藏。还开发了道路 4→34 o 34→3，挖掘了3 3 3号宝 藏。工程总代价为：1×1+1×1+1×2=41 imes 1 + 1 imes 1 + 1 imes 2 = 4 1×1+1×1+1×2=4
【样例解释2】
小明选定让赞助商打通了1 11 号宝藏屋。小明开发了道路 1→21 o 21→2，挖掘了 222 号宝 藏。开发了道路 1→31 o 31→3，挖掘了 333 号宝藏。还开发了道路 1→41 o 41→4，挖掘了4 4 4号宝 藏。工程总代价为：1×1+3×1+1×1=51 imes 1 + 3 imes 1 + 1 imes 1 = 51×1+3×1+1×1=5
【数据规模与约定】
对于20% 20%20%的数据： 保证输入是一棵树，1≤n≤81 le n le 81≤n≤8，v≤5000v le 5000v≤5000 且所有的 vv v都相等。
对于 40%40%40%的数据： 1≤n≤81 le n le 81≤n≤8，0≤m≤10000 le m le 10000≤m≤1000，v≤5000v le 5000v≤5000 且所有的v v v都相等。
对于70% 70%70%的数据： 1≤n≤81 le n le 81≤n≤8，0≤m≤10000 le m le 10000≤m≤1000，v≤5000v le 5000v≤5000
对于100% 100%100%的数据： 1≤n≤121 le n le 121≤n≤12，0≤m≤10000 le m le 10000≤m≤1000，v≤500000v le 500000v≤500000
其实这题是一个类似于状压的记忆化搜索
(prim)的错误性已经被多次提出，这里就不再说明，不过如果能拿到45pts也是很不错的
看到(1leq n leq 12)，大概也要想到对于所有经过的点进行状压
我们可以枚举出发点，同时用一个数组(f[i])记录状态为(i)时，所花费的最小代价
最后答案是(min(f[1<<n-1]))
同时我们记录一个(passed[i])表示有出发点到(i)所需经过的最少点数
对于每次搜索时我们传进去当前的状态(now)，同时枚举中间转移点(i)以及即将到达的点(j)
如果新的距离(f[now]+sq[i][j]*passed[i])大于原来的距离(f[now|1<<(j-1)])，那么就对新的状态继续搜索下去
一直做下去就可以得到结果
#include<iostream>
#include<string.h>
#include<string>
#include<stdio.h>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
using namespace std;
int sq[13][13],f[10100],n,passed[13],m;
int read()
{
int x=0,f=1;char ch=getchar();
while ((ch<'0') || (ch>'9')) {if (ch=='-') f=-1;ch=getchar();}
while ((ch>='0') && (ch<='9')) {x=x*10+(ch-'0');ch=getchar();}
return x*f;
}
void dfs(int now)
{
int i,j;
for (i=1;i<=n;i++)
{
if (now&(1<<(i-1)))
{
for (j=1;j<=n;j++)
{
if (!((1<<(j-1))&now) && (sq[i][j]!=1061109567) &&
(f[(1<<(j-1))|now]>f[now]+sq[i][j]*passed[i]))
{
int pre=passed[j];
passed[j]=passed[i]+1;
f[(1<<(j-1))|now]=f[now]+sq[i][j]*passed[i];
dfs((1<<(j-1))|now);
passed[j]=pre;
}
}
}
}
}
int main()
{
memset(sq,0x3f,sizeof(sq));
int i,ans=1e9+7;
n=read();m=read();
for (i=1;i<=m;i++)
{
int u=read(),v=read(),w=read();
if (w<sq[u][v]) sq[u][v]=sq[v][u]=w;
}
for (i=1;i<=n;i++)
{
memset(passed,0x3f,sizeof(passed));
memset(f,0x3f,sizeof(f));
passed[i]=1;f[(1<<(i-1))]=0;
dfs(1<<(i-1));
ans=min(ans,f[(1<<n)-1]);
}
printf("%d",ans);
return 0;
}