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