竟然模拟退火能做！我就直接抄代码了，我加了点注释。
题干：
题目描述 参与考古挖掘的小明得到了一份藏宝图，藏宝图上标出了 nn 个深埋在地下的宝藏屋， 也给出了这 nn 个宝藏屋之间可供开发的 mm 条道路和它们的长度。 小明决心亲自前往挖掘所有宝藏屋中的宝藏。但是，每个宝藏屋距离地面都很远， 也就是说，从地面打通一条到某个宝藏屋的道路是很困难的，而开发宝藏屋之间的道路 则相对容易很多。 小明的决心感动了考古挖掘的赞助商，赞助商决定免费赞助他打通一条从地面到某 个宝藏屋的通道，通往哪个宝藏屋则由小明来决定。 在此基础上，小明还需要考虑如何开凿宝藏屋之间的道路。已经开凿出的道路可以 任意通行不消耗代价。每开凿出一条新道路，小明就会与考古队一起挖掘出由该条道路 所能到达的宝藏屋的宝藏。另外，小明不想开发无用道路，即两个已经被挖掘过的宝藏 屋之间的道路无需再开发。 新开发一条道路的代价是： $$mathrm{L} imes mathrm{K}$$ L代表这条道路的长度，K代表从赞助商帮你打通的宝藏屋到这条道路起点的宝藏屋所经过的 宝藏屋的数量（包括赞助商帮你打通的宝藏屋和这条道路起点的宝藏屋） 。 请你编写程序为小明选定由赞助商打通的宝藏屋和之后开凿的道路，使得工程总代 价最小，并输出这个最小值。 输入输出格式 输入格式： 第一行两个用空格分离的正整数 $n,m$，代表宝藏屋的个数和道路数。 接下来 $m$ 行，每行三个用空格分离的正整数，分别是由一条道路连接的两个宝藏 屋的编号（编号为 $1-n$），和这条道路的长度 $v$。 输出格式： 一个正整数，表示最小的总代价。 输入输出样例 输入样例#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$ 号宝藏屋。小明开发了道路 $1 o 2$，挖掘了 $2$ 号宝 藏。开发了道路 $1 o 4$，挖掘了 $4$ 号宝藏。还开发了道路 $4 o 3$，挖掘了$ 3 $号宝 藏。工程总代价为：$1 imes 1 + 1 imes 1 + 1 imes 2 = 4 $ 【样例解释2】 小明选定让赞助商打通了$ 1$ 号宝藏屋。小明开发了道路 $1 o 2$，挖掘了 $2$ 号宝 藏。开发了道路 $1 o 3$，挖掘了 $3$ 号宝藏。还开发了道路 $1 o 4$，挖掘了$ 4 $号宝 藏。工程总代价为：$1 imes 1 + 3 imes 1 + 1 imes 1 = 5$ 【数据规模与约定】 对于$ 20\%$的数据： 保证输入是一棵树，$1 le n le 8$，$v le 5000$ 且所有的 $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$
代码：
#include <cstdio> #include <algorithm> #include <queue> #include <cstring> #define inf 2147483647 using namespace std; int n, m; int map[13][13]; int depth[13]; struct edge { int u, v; }; bool operator < (struct edge a, struct edge b) { return depth[a.u]*map[a.u][a.v]>depth[b.u]*map[b.u][b.v]; } int search(int source) { memset(depth, 0, sizeof(depth)); int vis[13]= {0}; priority_queue <struct edge> heap; edge past[1000]; int p = 0; struct edge e, e2; int cost = 0; depth[source]=1; vis[source]=1; for (int i = 1; i <= n; ++i) { if (map[source][i] < inf) { e.u = source; e.v = i; heap.push(e); } } for (int i = 1; i < n; ++i) { e = heap.top();//每次取当前最优解 heap.pop(); while (!heap.empty() && ((vis[e.v] || rand() % (n) < 1))) //注意这里的判断条件rand()%n<1,即对于一个当前最近点，不选择的几率随着n的增大而减小。 { if (!vis[e.v]) past[p++] = e; //对于跳过了的边，以后还用得上，等待选择结束后再压回优先队列中 e = heap.top(); heap.pop(); } vis[e.v] = 1; depth[e.v] = depth[e.u]+1; if (p-->0) //压回优先队列 { for (; p>=0; --p) { heap.push(past[p]); } } p = 0; for (int i = 1; i <= n; ++i) { if (map[e.v][i] < inf && !vis[i]) { e2.u = e.v; e2.v = i; heap.push(e2); } } cost += map[e.u][e.v] * depth[e.u]; } return cost; } int main() { int a, b, c; scanf("%d %d", &n, &m); for (int i = 1; i <= n; ++i) { for (int j = 1; j <= n; ++j) { map[i][j] = inf; } } for (int i = 0; i < m; ++i) { scanf("%d %d %d", &a, &b,&c); map[a][b] = map[b][a] = min(c, map[a][b]); } srand(201208);//瞎写的一个数，应该选什么数都差不多 int MIN = inf; for (int j = 1; j <1000; ++j) { //1000次运行是绝对万无一失的，事实上，400次就够了 for (int i = 1; i <= n; ++i) { MIN = min(MIN, search(i)); //枚举起点 } } printf("%d", MIN); return 0; }