---

宝藏(NOIP2017)

Description

参与考古挖掘的小明得到了一份藏宝图，藏宝图上标出了 n 个深埋在地下的宝藏屋， 也给出了这 n 个宝藏屋之间可供开发的m 条道路和它们的长度。

小明决心亲自前往挖掘所有宝藏屋中的宝藏。但是，每个宝藏屋距离地面都很远， 也就是说，从地面打通一条到某个宝藏屋的道路是很困难的，而开发宝藏屋之间的道路 则相对容易很多。

小明的决心感动了考古挖掘的赞助商，赞助商决定免费赞助他打通一条从地面到某 个宝藏屋的通道，通往哪个宝藏屋则由小明来决定。

在此基础上，小明还需要考虑如何开凿宝藏屋之间的道路。已经开凿出的道路可以 任意通行不消耗代价。每开凿出一条新道路，小明就会与考古队一起挖掘出由该条道路 所能到达的宝藏屋的宝藏。另外，小明不想开发无用道路，即两个已经被挖掘过的宝藏 屋之间的道路无需再开发。

新开发一条道路的代价是：

\[L×K\]

L代表这条道路的长度，K代表从赞助商帮你打通的宝藏屋到这条道路起点的宝藏屋所经过的 宝藏屋的数量（包括赞助商帮你打通的宝藏屋和这条道路起点的宝藏屋） 。

请你编写程序为小明选定由赞助商打通的宝藏屋和之后开凿的道路，使得工程总代 价最小，并输出这个最小值。

Input Format

第一行两个用空格分离的正整数 n,m，代表宝藏屋的个数和道路数。

接下来 m 行，每行三个用空格分离的正整数，分别是由一条道路连接的两个宝藏 屋的编号（编号为 1−n），和这条道路的长度 v。

Output Format

一个正整数，表示最小的总代价。

Sample Input

4 5 1 2 1 1 3 3 1 4 1 2 3 4 3 4 1

Sample Output

4

解析

简单概括题意：给出一副无向图,每条边都有一个权值且均未开通,先可以随便取一个起点,要开通一些边,使它成为一个连通图,开通一条边的代价为这条边的权值*起点到它的点的个数(起点也算),求最小代价。

数据范围\(N<=12\)，基本上可以确定是状压\(DP\)了。我们直接最简单地设置状态:\(f[S]\)代表以及取的节点的状态为S的最小代价，那么目标状态就是\(f[(1<<n)-1]\)。

如果考虑递推求解的话，我们发现需要计算花费的深度会很难枚举，这就导致了\(DP\)顺序的问题，如果选择用记忆化搜索求解的话，会方便很多。

由于起点不是确定的，我们需要用一重循环来枚举起点，然后以\(1<<(root-1)\)为初始状态，对每一种情况进行一次记忆化搜索，记搜的大体思路如下：

1.对于状态\(S\)，枚举一个点\(i\)，满足\(i \in S\)

2.在枚举一个点\(j\)，满足\(i,j\)有边相连且\(j \notin S\)

3.状态转移方程:\(f[S']=min{f[S]+depth[i]*dis[i][j]}\)

4.更新新加入的节点j的深度

5.搜索下一个状态\(S'\)

6.回溯还原节点j的深度

最后在每一种情况的目标状态中取个\(min\)就是最终的答案了，时间复杂度\(O(n^32^n)\)。

\(Code:\)

#include
    
     using namespace std;const int N=15,M=10015,Smax=(1<
     
      f[S]+depth[i]*dis[i][j])                    {                        int temp=depth[j];                        depth[j]=depth[i]+1;                        f[S|(1<<(j-1))]=f[S]+depth[i]*dis[i][j];                        Search(S|(1<<(j-1)));                        depth[j]=temp;                    }                                   }            }        }    }}inline void solve(void){    for(int root=1;root<=n;root++)    {        memset(f,0x3f,sizeof f);        memset(depth,0x3f,sizeof depth);        f[1<<(root-1)]=0;        depth[root]=1;        Search(1<<(root-1));        ans=min(ans,f[(1<
     
    

---