一道图的题目

给一个图， 给定源节点， 要求在图里面选择一定的边数， 保证每个节点都有原来图的最短路径。 求边数和的最小值。 想问下， 先求单源最短路径， 松弛的时候，遇到两个前驱节点到当前节点，最短路径一样的情况，直接选择前驱节点到当前节点长度短的那个。 最后再遍历所有节点到前驱到自己的边，累加。 是不是就是要求的最小和？
全部评论
我咋觉得就是dijkstra和prim一起算，这俩算法本身就差在数组里保存的是啥，优先dijkstra，dijkstra可加入多个点时，以prim选节点加入。
点赞 回复 分享
发布于 2016-09-12 02:00

相关推荐

昨天 10:57
华东理工大学 Java
点赞 评论 收藏
分享
02-24 15:49
vivo_运营_HR
vivo26届实习内推
不得不说今年实习开的真早， 这才刚开学暑期实习和日常实习就开了，26届的同学估计还没做好准备，可以先mark这篇帖子，后面有空来这里取内推码投递 看一一下实习岗位还是蛮多，hc算中等设计类 研发类 供应链类 产品运营类 市场类都覆盖了。 工作地点广东江苏等地都有，有能力的一定要投一下实习，直接转正就不用操心秋招了，真的挺爽，至少心里能踏实的再找其他工作入职vivo有一段时间了，强度是有一些，但是平时总有一些时候比如一些活动，聚会之类的能让人感觉到放松，上班的心态和学生区别还是很大的，大家现在投简历虽然累，之后还有一个暑假可以好好享受呢 ，别怕今年校招生住工业园C区，环境如图，环境尚可...
投递vivo等公司10个岗位 >
点赞 评论 收藏
分享
02-19 19:32
哈尔滨剑桥学院 管理培训生
本科 双非 25应届有什么好工作吗
数开小菜鸡：你是我今早见过的最美的牛客女孩......
点赞 评论 收藏
分享
02-25 17:25
广州中医药大学 安卓
简历这些坑千万别踩-简历优化，思路详解
这期简历优化实战案例是来自一位双非本科的社招同学,求职岗位软件测试工程师,意向互联网想来看看这位同学的简历：优化后的简历：一起来看坑点和如何避坑：结构坑点1.冗余个人信息:学历不用在个人信息和教育背景中重复写2.过多掌握技能:"专业技能"是技术简历的第一大坑最佳实践是在项目工作中展示,详见我另一篇笔记,移除3.主观自我评价:"自我评价"是第二大坑!。它是主观的,面试官无法从简历中验证真实性和匹配度,移除排版设计坑点1.排版结构不一:尽量使用上下一种结构,而非左右上下结构2.时间位置不当:中文是从左到右阅读,左侧是视觉重点,放公司等高优信息,时间放在右侧专...
投递完美世界等公司10个岗位 > 投了多少份简历才上岸 简历中的项目经历要怎么写
点赞 评论 收藏
分享
评论
点赞
收藏
分享

全站热榜

更多

创作者周榜

更多
正在热议
更多
# 如何KTV领导 #
31338次浏览 255人参与
# 研究所笔面经互助 #
55078次浏览 395人参与
# 掌阅春招 #
88759次浏览 515人参与
# 你投递的公司有几家约面了？ #
39080次浏览 228人参与
# 软开人，秋招你打算投哪些公司呢 #
66916次浏览 716人参与
# 生物制药/化工校招攻略 #
33764次浏览 265人参与
# 硬件/芯片公司工作体验 #
58463次浏览 560人参与
# 当下环境，你会继续卷互联网，还是看其他行业机会 #
72540次浏览 539人参与
# 软件开发春招备战日记 #
57572次浏览 493人参与
# 如何缓解入职前的焦虑 #
141606次浏览 1126人参与
# 你最近一次加班是什么时候？ #
31838次浏览 250人参与
# 你遇到过哪些神仙同事 #
45118次浏览 425人参与
# vivo求职进展汇总 #
167847次浏览 1020人参与
# 产品每日一题 #
29040次浏览 404人参与
# 考研人，我有话说 #
14657次浏览 282人参与
# 你今年的平均薪资是多少？ #
94236次浏览 462人参与
# TP-LINK工作体验 #
38497次浏览 786人参与
# 还记得你第一次面试吗？ #
75882次浏览 1094人参与
# 秋招白月光 #
52700次浏览 776人参与
# 上班苦还是上学苦呢？ #
201332次浏览 1236人参与
# 想给25届机械人的秋招建议 #
22488次浏览 203人参与
牛客网
牛客企业服务