题目描述
参与考古挖掘的小明得到了一份藏宝图，藏宝图上标出了 \(n\) 个深埋在地下的宝藏屋， 也给出了这 \(n\) 个宝藏屋之间可供开发的 \(m\) 条道路和它们的长度。
小明决心亲自前往挖掘所有宝藏屋中的宝藏。但是，每个宝藏屋距离地面都很远， 也就是说，从地面打通一条到某个宝藏屋的道路是很困难的，而开发宝藏屋之间的道路 则相对容易很多。
小明的决心感动了考古挖掘的赞助商，赞助商决定免费赞助他打通一条从地面到某 个宝藏屋的通道，通往哪个宝藏屋则由小明来决定。
在此基础上，小明还需要考虑如何开凿宝藏屋之间的道路。已经开凿出的道路可以 任意通行不消耗代价。每开凿出一条新道路，小明就会与考古队一起挖掘出由该条道路 所能到达的宝藏屋的宝藏。另外，小明不想开发无用道路，即两个已经被挖掘过的宝藏 屋之间的道路无需再开发。
新开发一条道路的代价是：
\]
\(L\)代表这条道路的长度，\(K\)代表从赞助商帮你打通的宝藏屋到这条道路起点的宝藏屋所经过的 宝藏屋的数量（包括赞助商帮你打通的宝藏屋和这条道路起点的宝藏屋） 。
请你编写程序为小明选定由赞助商打通的宝藏屋和之后开凿的道路，使得工程总代 价最小，并输出这个最小值。
输入输出格式
输入格式
第一行两个用空格分离的正整数 \(n\),\(m\),代表宝藏屋的个数和道路数。
接下来 \(m\) 行，每行三个用空格分离的正整数，分别是由一条道路连接的两个宝藏 屋的编号（编号为 \(1\sim n\)），和这条道路的长度 \(v\)。
输出格式
一个正整数，表示最小的总代价。
数据范围
对于 \(20\%\)的数据： 保证输入是一棵树，\(1 \le n \le 8\)，\(v \le 500\)且所有的 \(v\) 都相等。
对于 \(40\%\)的数据： \(1 \le n \le 8\)，\(0 \le m \le 1000\)，\(v \le 5000\)且所有的 \(v\) 都相等。
对于 \(70\%\)的数据： \(1 \le n \le 8\) ,\(0 \le m \le 1000\)，\(v \le 5000\)。
对于 \(100\%\)的数据：\(1 \le n \le 12\), \(0 \le m \le 1000\)，\(v \le 500000\)。
题解
看题第一眼，Prime，但是发现Prime是错的，Prime的贪心准则不符合这道题，看一眼数据范围\(1 \le n \le 12\),我们可以用状态压缩，\(f[i][j]\)表示当前已探索的点集为i上一层的点集为j，这样的状态转移就十分简单了，但是，如果仅仅是这样，我们是过不了\(100\%\)的数据的，我们来想办法压一下维，我们考虑一下能否把第二维压去，但是，我们会发现，这样的话，对于在集合\(i\)中的点，我们就没有办法直接判定它是在那一层中的。所以我们每次转移时还需要枚举上一层的状态。
代码
#include<bits/stdc++.h>
using namespace std;
long long dist[15][15];
struct Data{
long long sum;
int dist[15];
}dp[1 << 13];
long long inf, ans = 0x7ffffffff;
int main()
{
memset(dist, 0x7f, sizeof(dist));
inf = dist[0][0];
int n, m, x, y;
long long w;
scanf("%d%d", &n, &m);
for(int i = 1; i <= m; ++ i)
{
scanf("%d%d%lld", &x, &y, &w);
dist[x][y] = dist[y][x] = min(dist[x][y], w);
}
int U = (1 << n) - 1;
for(int root = 1; root <= n; ++ root)
{
memset(dp, 0x3f, sizeof(dp));
dp[1 << (root - 1)].dist[root] = 1, dp[1 << (root - 1)].sum = 0;
for(int i = 0; i <= U; ++ i)
{
int S = i | (1 << (root - 1));
for(int u = 1; u <= n; ++ u)
if((S & (1 << (u - 1))))
for(int v = 1; v <= n; ++ v)
if((dist[u][v] != inf) && (!(S & (1 << (v - 1)))))
if(dp[S | (1 << (v - 1))].sum > dp[S].sum + dist[u][v] * ((long long)dp[S].dist[u]))
{
dp[S | (1 << (v - 1))] = dp[S];
dp[S | (1 << (v - 1))].sum = dp[S].sum + dist[u][v] * ((long long)dp[S].dist[u]);
dp[S | (1 << (v - 1))].dist[v] = dp[S | (1 << (v - 1))].dist[u] + 1;
}
}
ans = min(ans, dp[U].sum);
}
printf("%lld\n", ans);
}