【模板】Floya
题目描述：
给定一个n个点m条边的无向图，图中可能存在重边和自环，边权可能为负数。
求最小生成树的树边权重之和，如果最小生成树不存在则输出impossible。
给定一张边带权的无向图=(V,E)，其中V表示图中点的集合，E表示图中边的集合，n=|V\，m =|E。
由V中的全部n个顶点和E中n―1条边构成的无向连通子图被称为G的一棵生成树，其中边的权值之和最小的生成树被称为无向图的最小生成树。
输入格式：
第一行包含两个整数n和m。
接下来m行，每行包含三个整数u, v, ww，表示点u和点v之间存在一条权值为w的边。
输出格式：
共一行，若存在最小生成树，则输出一个整数，表示最小生成树的树边权重之和，如果最小生成树不存在则输出impossible 。
数据范围：
输入样例：
4 5 1 2 1 1 3 2 1 4 3 2 3 2 3 4 4
输出样例：
6
参考题解 ：
from collections import defaultdict, deque def find(x): if not p[x] == x: p[x] = find(p[x]) return p[x] n, m = map(int, input().split()) p = [_ for _ in range(n + 1)] g = [] for _ in range(m): g.append(tuple(map(int, input().split()))) g.sort(key=lambda x:x[2]) cnt = 0 res = 0 for u, v, w in g: eu = find(u) ev = find(v) if eu == ev: continue p[ev] = eu res += w cnt += 1 print('impossible') if not cnt == n - 1 else print(res)
完毕！
如果觉得有用，麻烦大家三连一下，谢谢！
