欢迎来到起遇信息学
起遇信息学正处于上线筹建阶段，以下功能已全部开放免费体验： ✅ 完整题库浏览与代码提交评测（C / C++ / Python / Java 等） ✅ 入门到进阶的系列课程试读、作业与考试 ✅ AI 提示、AI 作业分析等智能助教功能 ✅ 赛事模拟与个人能力报告 ✅ 邮箱注册开放 ⏳ 付费课程订阅与微信/支付宝支付通道 ⏳ 手机号登录，微信扫码登录、微信公众号绑定 使用中如遇任何问题，欢迎通过页面底部 **"联系我们"** 与我们沟通。
Make It Connected
CF1095F Make It Connected
题目描述
有 n 个顶点，顶点 i 上写着正整数 a_i。初始图中没有边。
可以为任意两个不同顶点 x,y 加边，普通代价为 a_x+a_y。另外有 m 个特价方案，可以花 w 连接指定的 x,y。特价方案可以不用。
求使整张图连通的最小总代价。
输入格式
第一行 n,m (1 <= n <= 200000, 0 <= m <= 200000)。
第二行 n 个整数 a_i (1 <= a_i <= 10^12)。
接下来 m 行，每行 x,y,w (x != y, 1 <= w <= 10^12)，表示一个特价连边方案。
输出格式
输出使图连通的最小总代价。
样例
3 2
1 3 5
1 2 2
2 3 1
3
在线编程 IDE
建议全屏模式获得最佳体验
键盘快捷键
| 进入全屏编程 | Alt+E |
| 递交评测 | Ctrl+Enter |
| 注释/取消注释 | Ctrl+/ |
| 缩放字体 | Ctrl+滚轮 |
第 1 行，第 1 列
0 字符
-
最近自测结果
暂未运行
最近递交结果
暂无递交记录