农夫约翰要把他的牛奶运输到各个销售点。
运输过程中，可以先把牛奶运输到一些销售点，再由这些销售点分别运输到其他销售点。
运输的总距离越小，运输的成本也就越低。
低成本的运输是农夫约翰所希望的。
不过，他并不想让他的竞争对手知道他具体的运输方案，所以他希望采用费用第二小的运输方案而不是最小的。
现在请你帮忙找到该运输方案。
注意：：
第一行是两个整数?N,M，表示销售点数和交通线路数；
接下来?M?行每行?3?个整数?x,y,z，表示销售点?x?和销售点?y?之间存在线路，长度为?z。
输出费用第二小的运输方案的运输总距离。
1≤N≤500,
1≤M≤104,
1≤z≤109,
数据中可能包含重边。
4 4
1 2 100
2 4 200
2 3 250
3 4 100
450题目要求求一棵次小生成树。
具体操作：
1.求最小生成树，统计标记每条边时树边，还是非树边；同时把最小生成树建出来。
2.预处理最小生成树上任意两点间的边权最大值dist[a][b]
3.依次枚举所有非树边，求min(sum+w-dist[a][b]),满足w>dist[a][b]。
O（mlogm+n^2）
为什么要求出次大距离，只求最大距离不可以吗？
在算法中，求解每个点到其它点的最大距离和次大距离的目的是为了在后续遍历不在最小生成树中的边时，能够利用这些信息进行计算，找到替换权值最小的边。
具体来说，对于一条边 (a, b, w)，假设 a 和 b 已经在最小生成树中，而当前边 (a, b, w) 不在最小生成树中。我们可以分两种情况讨论：
1. 如果 w 大于 a 到 b 的最大距离，那么替换后的生成树权值为当前生成树的总权值加上 w 减去 a 到 b 的最大距离，因为 w 大于最大距离，所以替换后生成树的总权值会减小。
2. 如果 w 大于 a 到 b 的次大距离，那么替换后的生成树权值为当前生成树的总权值加上 w 减去 a 到 b 的次大距离，同样因为 w 大于次大距离，所以替换后生成树的总权值会减小。
所以，为了确保找到替换权值最小的边，需要同时计算每个点到其它点的最大距离和次大距离。这样在遍历不在最小生成树中的边时，可以根据这些信息选择合适的边进行替换，以得到次小生成树的权值。
存不存在w小于次小距离的情况？
在上述算法中，每次替换边时，比较的是当前边的权值 `w` 和当前边两端点之间的次大距离。这样设计的目的是为了确保替换后的生成树总权值减小，从而找到次小生成树。
在实际情况中，存在一种特殊情况，即如果 `w` 恰好等于当前边两端点之间的次大距离，那么替换后的生成树总权值将保持不变。这是因为 `w` 和次大距离相等，替换后总权值的变化为 `w - dist2[a][b]`，等于零。
因此，可以说不存在 `w` 严格小于次小距离的情况。如果 `w` 等于次大距离，替换后总权值不变；如果 `w` 大于次大距离，替换后总权值减小。这样设计可以确保算法找到的次小生成树是在最小生成树的基础上替换一条边而得到的。
#include<iostream>
#include<string>
#include<cstring>
#include<cmath>
#include<ctime>
#include<algorithm>
#include<utility>
#include<stack>
#include<queue>
#include<vector>
#include<set>
#include<math.h>
#include<map>
#include<sstream>
#include<deque>
#include<unordered_map>
using namespace std;
typedef long long LL;
const int N = 505, M = 2e4 + 5;
int n, m;
struct Edge {
int a, b, c;
bool f;
bool operator<(const Edge& t)const {
return c < t.c;
}
}edge[M];
int dist1[N][N], dist2[N][N];
int fa[N];
int h[N], e[M], w[M], ne[M], idx;
void add(int a, int b, int c) {
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}
int find(int a) {
if (fa[a] == a)return a;
return fa[a] = find(fa[a]);
}
void dfs(int u, int f, int mx1, int mx2, int d1[], int d2[]) {
d1[u] = mx1, d2[u] = mx2;
for (int i = h[u]; i != -1; i = ne[i]) {
int j = e[i];
if (j != f) {
int t1 = mx1, t2 = mx2;
if (mx1 < w[i]) {
t2 = t1, t1 = w[i];
}
else if (mx2 < w[i] && w[i] < mx1) {
t2 = w[i];
}
dfs(j, u, t1, t2, d1, d2);
}
}
}
int main() {
cin >> n >> m;
memset(h, -1, sizeof h);
for (int i = 1, a, b, c; i <= m; i++) {
scanf("%d%d%d", &a, &b, &c);
edge[i] = { a,b,c };
}
for (int i = 1; i <= n; i++) fa[i] = i;
sort(edge + 1, edge + 1 + m);
LL sum = 0;
for (int i = 1; i <= m; i++) {
int a = edge[i].a, b = edge[i].b, c = edge[i].c;
int pa = find(edge[i].a), pb = find(edge[i].b);
if (pa != pb) {
sum += c;
fa[pa] = pb;
add(a, b, c), add(b, a, c);
edge[i].f = 1;
}
}
for (int i = 1; i <= n; i++) dfs(i, -1, -1e9, -1e9, dist1[i], dist2[i]);
LL ret = 1e18;
for (int i = 1; i <= m; i++) {
if (!edge[i].f) {
int a = edge[i].a, b = edge[i].b, c = edge[i].c;
LL t;
if (c > dist1[a][b]) {
t = sum + c - dist1[a][b];
}
else if (c > dist2[a][b]) {
t = sum + c - dist2[a][b];
}
ret = min(ret, t);
}
}
cout << ret << endl;
return 0;
}