首页 > 其他分享 >点亮须弥【UUST】

点亮须弥【UUST】

时间:2024-09-03 12:50:55浏览次数:11  
标签:点亮 ans 旅行者 须弥 UUST 传送点 find

问题描述

原神 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

相关文章

  • 小青蛙的故事【UUST】
    问题描述小青蛙爱唱歌,呱呱呱,呱呱呱,唱的荷花快快长,唱的西瓜快快长。荷花开了当舞台,西瓜长大做房子!但是,小青蛙觉得每天都在池塘边唱歌好无聊,就想像妈妈一样出去工作。有一天,小青蛙独自出门学习邻居青蛙叔叔们捉害虫,但是由于缺少锻炼,一天下来累坏咱们小青蛙了。小青蛙还是想......
  • Scratch中的数据可视化:点亮编程与艺术的火花
    标题:Scratch中的数据可视化:点亮编程与艺术的火花在数字时代,数据可视化不仅是一种技术,更是一门艺术。Scratch,这款由麻省理工学院媒体实验室开发的编程工具,以其独特的视觉化编程方式,为孩子们开启了编程与艺术结合的大门。本文将详细探讨Scratch是否支持通过编程实现数据可视化......
  • 实验11:点阵屏点亮7
    使用了点阵屏字模提取软件选择列扫描,c51模式,8*8得到的序列用于程序中的数组硬件接线图代码:main.c#include<reg52.h>typedefunsignedintu16;typedefunsignedcharu8;#defineDZ_LED_LP0sbitrCLK=P3^5;sbitSRCLK=P3^6;sbitSER=P3^4;u8DZ_code[]={0x0......
  • 基于STM32的寄存器实现点亮LED--基于RUST实现
    main.rs#![no_std]#![no_main]usecore::ptr;usecortex_m_rt::entry;usepanic_haltas_;//当发生panic时停止执行//定义寄存器地址constRCC_BASE:u32=0x40021000;constGPIOB_BASE:u32=0x40010C00;constRCC_APB2ENR_OFFSET:u32=0x18;constGPIOB......
  • 基于STM32的寄存器实现点亮LED
    1.启动文件startup_stm32f103xe.s;********************(C)COPYRIGHT2017STMicroelectronics********************;*FileName:startup_stm32f103xe.s;*Author:MCDApplicationTeam;*Description:STM32F103xEDevicesvectort......
  • 点亮职场之路,从优化简历开始 —— 专业Java简历优化服务,助您脱颖而出
    手机或电脑浏览器就可以打开,面霸宝典【全拼音】.com这里可以优化简历,模拟面试,企业项目源码,最新最全大厂高并发面试题,项目场景题,算法题,底层原理题在Java技术的浩瀚星海中,每一位求职者都是独特的星辰,但如何让自己在众多候选人中熠熠生辉,成为企业争抢的“宝藏”?答案,就藏在......
  • 点亮你心中的灯
    自从工作距离我挺遥远后,突然萌发一个想法,要不试下搞搞硬件看能否可行。于是在某宝购买了一套器件。首先将面包板电源按照正负极方向插入面板板中,接入12V的DC电源。而电阻一极插入正极,另一极插入到中间位置。而二极管一极插入正极,另一极插入到中间位置。因为面包板中间部分垂直通......
  • 点亮童梦思考之光,神秘伙伴震撼登场!
    本文由ChatMoney团队出品介绍说明咱们来聊聊“十万个为什么”机器人,这对小朋友来说,好处可多了去啦!小朋友们天生好奇,满脑子都是问号。这个机器人就像个啥都懂的知识达人,不管他们问啥,都能给出答案。从天上的星星为啥发光,到水里的鱼儿为啥游来游去,统统都能讲清楚。这不仅让小......
  • 《CSS创意项目实战指南》:点亮网页,从实战中掌握CSS的无限创意
    CSS创意项目实战指南在数字时代,网页不仅是信息的载体,更是艺术与技术的融合体。通过CSS,你可以将平凡的网页转变为引人入胜的视觉盛宴,让用户体验跃升至全新高度。《CSS创意项目实战指南》正是这样一本引领你探索CSS无限可能的实战宝典。一、启航CSS创意之旅本书精心设计了12......
  • 【RK3568】点亮eDP屏幕+双屏异显
    一、驱动eDP屏幕    一般来说,屏幕的规格书中会找到屏幕的相关参数,如没有,也可直接找屏幕厂商要,首先打开屏幕的规格书,搜索EDIDTable,可找到如下信息:    (1)显示时序配置        将这些参数对应到设备树中,即可完成下面修改,关键节点就是显示时序配置的d......