问题描述
原神 3.03.0 版本马上就要到来,须弥地图即将开放。
神秘少女纳西坦答应荧,如果她能以最快的速度点亮须弥所有的传送点,就可以和小吉祥草王贴贴。
岩之魔神摩拉克斯非常好心地送来了须弥的地图,地图上有 nn 个传送点,分别标注为 1∼n1∼n,旅行者荧可以在已经点亮的传送点之间瞬间传送。
特别地,当旅行者来到须弥的范围中时,传送点 11 会自动点亮,并开始计时。
见多识广的风之魔神温迪告诉旅行者,须弥地形复杂,有沙漠,有雨林,有的道路非常难走,并且很容易迷失方向,或者因体力不支而倒下。最终,他们讨论出了 mm 条可以行走的路径(路径是双向的),第 ii 条路径连接传送点 ui,viui,vi,需要花费 wiwi 分钟到达。
最后,旅行者向雷之魔神借用了她的人偶作为计算机,但她根本不会使用。
旅行者向你寻求帮助。作为回报,她会给你三份甜甜花酿鸡。
但是你觉得旅行者给的太少,决定只告诉她最快多快能点亮须弥,不告诉她具体应该怎么走。
输入格式
输入第 11 行包含两个正整数nn 和 mm,分别表示地图传送点的个数以及边数。
第 2∼m+12∼m+1 行每行包含三个整数 ui,vi,wiui,vi,wi,表示 uiui 和 vivi 之间有一条需要走 wiwi 分钟的路。
输出格式
输出一行,这一行只包含一个整数,表示最快多少分钟能够点亮须弥所有传送阵;如果永远无法点亮全部传送阵的话,输出 −1−1。
样例输入
4 5
1 2 2
1 3 2
1 4 3
2 3 4
3 4 3
样例输出
7
def find(x):
if x != p[x]:
p[x] = find(p[x])
return p[x]
def merge(x,y):
xroot = find(x)
yroot = find(y)
if xroot != yroot:
p[yroot] = xroot
n,m = map(int,input().split())
p = list(range(n+1))
Edge = []
for i in range(m):
u,v,w = map(int,input().split())
Edge.append((w,u,v))
Edge.sort()
ans = 0
num = 0
for w,u,v in Edge:
uroot = find(u)
vroot = find(v)
if uroot != vroot:
num+=1
merge(u,v)
ans += w
if num != n-1:
ans = -1
print(ans)
标签:点亮,ans,旅行者,须弥,UUST,传送点,find From: https://blog.csdn.net/weixin_72050316/article/details/141858564