1. 问题描述：

农夫约翰要把他的牛奶运输到各个销售点。运输过程中，可以先把牛奶运输到一些销售点，再由这些销售点分别运输到其他销售点。运输的总距离越小，运输的成本也就越低。低成本的运输是农夫约翰所希望的。不过，他并不想让他的竞争对手知道他具体的运输方案，所以他希望采用费用第二小的运输方案而不是最小的。现在请你帮忙找到该运输方案。注意：：

• 如果两个方案至少有一条边不同，则我们认为是不同方案；
• 费用第二小的方案在数值上一定要严格大于费用最小的方案；
• 答案保证一定有解；

输入格式

第一行是两个整数 N,M，表示销售点数和交通线路数；接下来 M 行每行 3 个整数 x,y,z，表示销售点 x 和销售点 y 之间存在线路，长度为 z。

输出格式

输出费用第二小的运输方案的运输总距离。

数据范围

1 ≤ N ≤ 500，
1 ≤ M ≤ 10 ^ 4，
1 ≤ z ≤ 10 ^ 9,

数据中可能包含重边。

输入样例：

4 4
1 2 100
2 4 200
2 3 250
3 4 100

输出样例：

450
来源：https://www.acwing.com/problem/content/description/1150/

2. 思路分析：

3. 代码如下：

from typing import Listclass Soltution:# dfs求解当前节点u到其余点的最大边权与次打边权def dfs(self, u: int, p: int, maxd1: int, maxd2: int, dis1: List[int], dis2: List[int], e: List[List[int]]):dis1[u], dis2[u] = maxd1, maxd2for next in e[u]:if next[0] != p:w = next[1]# 注意这里需要先备份一下maxd1和maxd2因为后面还需要遍历其他的邻接点如果直接修改会造成答案错误td1, td2 = maxd1, maxd2if w > td1:td2 = td1td1 = welif td1 > w > td2:td2 = wself.dfs(next[0], u, td1, td2, dis1, dis2, e)# 并查集查找x的父节点并且进行路径压缩def find(self, x: int, fa: List[int]):if x != fa[x]:fa[x] = self.find(fa[x], fa)return fa[x]def process(self):n, m = map(int, input().split())# w存储题目中输入的图, e来存储图中的最小生成树, 方便后面dfs枚举计算任意两点之间的距离w = list()for i in range(m):a, b, c = map(int, input().split())# w的第四个参数为是否是最小生成树中边的标记, 0为非树边, 1为树边w.append([a, b, c, 0])# 根据边权从小到大排序w.sort(key=lambda x: x[2])# kruskal算法# fa为kruskal的父节点列表e = [list() for i in range(n + 1)]fa = [i for i in range(n + 1)]s = 0for i in range(m):a, b, c = self.find(w[i][0], fa), self.find(w[i][1], fa), w[i][2]if a != b:fa[a] = b# 标记一下是树边w[i][3] = 1# 构造最小生成树也即将其存储到w中, 因为是无向边所以需要创建两个方向的边e[w[i][0]].append((w[i][1], c))e[w[i][1]].append((w[i][0], c))# s计算最小生成树的权值s += c# dis1, dis2分别记录两个点之间边权的最大值与次大值dis1, dis2 = [[0] * (n + 1) for i in range(n + 1)], [[0] * (n + 1) for i in range(n + 1)]# dfs方法的第一个参数为起点, 第二个参数因为是无向边所以需要传递一个父节点参数防止dfs死循环# 第三/四个参数为从当前起点为i出发的最大值和次大值for i in range(1, n + 1):self.dfs(i, -1, 0, 0, dis1[i], dis2[i], e)# 枚举非树边res = 10 ** 20for i in range(m):a, b, c, d = w[i][0], w[i][1], w[i][2], w[i][3]# 当d为非树边的时候判断属于哪一种情况, 如果非树边与当前环中的最大边相等说明需要尝试加入次大边if d == 0:t = 0if c > dis1[a][b]:t = s + c - dis1[a][b]elif c > dis2[a][b]:t = s + c - dis2[a][b]res = min(res, t)return resif __name__ == "__main__":print(Soltution().process())