描述
南阳理工学院要进行用电线路改造,现在校长要求设计师设计出一种布线方式,该布线方式需要满足以下条件:
1、把所有的楼都供上电。
2、所用电线花费最少
输入
第一行是一个整数n表示有n组测试数据。(n<5)
每组测试数据的第一行是两个整数v,e.
v表示学校里楼的总个数(v<=500)
随后的e行里,每行有三个整数a,b,c表示a与b之间如果建铺设线路花费为c(c<=100)。(哪两栋楼间如果没有指明花费,则表示这两栋楼直接连通需要费用太大或者不可能连通)
随后的1行里,有v个整数,其中第i个数表示从第i号楼接线到外界供电设施所需要的费用。( 0<e<v*(v-1)/2 )
(楼的编号从1开始),由于安全问题,只能选择一个楼连接到外界供电设备。
数据保证至少存在一种方案满足要求。
输出
每组测试数据输出一个正整数,表示铺设满足校长要求的线路的最小花费。
样例输入
1
4 6
1 2 10
2 3 10
3 1 10
1 4 1
2 4 1
3 4 1
1 3 5 6样例输出
4
代码:
prim算法:
并查集:
分享到:
相关推荐
动态规划:http://acm.zju.edu.cn/forum/viewtopic.php?t=69 搜索:http://acm.zju.edu.cn/forum/viewtopic.php?t=67 数论:http://acm.zju.edu.cn/forum/viewtopic.php?t=66 几何:...
ACM大量习题题库 现在网上有许多题库,大多是可以在线评测,所以叫做Online Judge。除了USACO是为IOI准备外,其余几乎全 部是大学的ACM竞赛题库。 USACO http://ace.delos.com/usacogate 美国著名在线题库,专门为...
浙江大学在线题库:http://acm.zju.edu.cn/problems.php 浙江工业大学在线题库:http://acm.zjut.edu.cn 衡阳市第八中学信息学奥赛论坛&zju译题站:http://61.187.179.132:82/ UVA在线题库:...
In this problem, you are asked to implement this. The following commands need to be supported: BACK: Push the current page on the top of the forward stack. Pop the page from the top of the backward...
(我现在主要在CSDN上整理计算机安全、软件工程(可信软件)、系统及通信方面的论文及相关理论书籍,如果对这方面内容感兴趣,可以访问:http://qysh123.download.csdn.net/ 查看我上传的所有资料。内容比较多,需要...
In the present world you frequently meet a lot of call numbers and they are going to be longer and longer. You need to remember such a kind of numbers. One method to do it in an easy way is to assign ...
http://blog.csdn.net/acmmmm
zju 1048 Financial Managementhttp://acm.zju.edu.cn/show_problem.php?pid=1048
TagRec won the best poster award @ Hypertext 2014 (HT'14) conference: http://ht.acm.org/ht2014/index.php?awards.poster TagRec is also a main part of the recommender systems in the Layers project ...
:로풀어보기: ://www.acmicpc.net/step 방온라인SDS방온라인스터디: ://www.acmicpc.net/group/workbook/list/9962 본반기본반: ://www.acmicpc.net/workbook/view/2047 고득점로그래머스고득점工具包: ://...
(我现在主要在CSDN上整理计算机安全、软件工程(可信软件)、系统及通信方面的论文及相关理论书籍,如果对这方面内容感兴趣,可以访问:http://qysh123.download.csdn.net/ 查看我上传的所有资料。内容比较多,需要...
408复试刷题 这个项目是我在2021年考研时的刷题集锦,其中包括王道机试指南第二版以及杭电OJ,前期用的C语言,后续改用C++,感谢作者炉灰 ...例题2.5 叠筐 http://acm.hdu.edu.cn/showproblem.php?pid=2
本资源包括项目演示视频、源代码、说明文档、项目资源。 本场景是一个篮球场,篮球可以做自由落体运动和反弹。 场景涉及灯光,纹理,摄像...具体细节可看博客:https://blog.csdn.net/A_ACM/article/details/100569142
3、林杰博客说明:http://linjie.org/2015/08/06/amr%E6%A0%BC%E5%BC%8F%E8%BD%ACmp3%E6%A0%BC%E5%BC%8F-%E5%AE%8C%E7%BE%8E%E8%A7%A3%E5%86%B3Linux%E4%B8%8B%E8%BD%AC%E6%8D%A20K%E9%97%AE%E9%A2%98/
湖南大学ACM-OJ的部分题目代码,对学习数据结构和算法很有帮助
題目: http://acm.pku.edu.cn/JudgeOnline/problem?id=2418
百柱在线裁判 문제on관리관기저장소입니다。 1일1커밋용 Python목적 Python및리알고
训练赛网址https://acm.zcmu.edu.cn/JudgeOnline/contest.php?cid=1343
pascal source code for http://acm.pku.edu.cn/JudgeOnline/problem?id=3728