得物9.24笔试,ak,第三题做法分享

代码如下,
解法就是维护最短路生成树,做dijkstral的时候标记一下哪些边用过就好,唯一注意的点是当dist相同,都可以更新下一个点的最短路时,优先使用原先就有的m条边转移过来的,这部分体现到代码里就是给每条边都编号了,m条边的边的号比k条边的小,然后heap的排序优先级为距离 > 边号 > 当前点,这样每次都会让m条边的排在前面

代码是回忆版,部分地方小bug:
开始heap循环前加上一行dist【1】=0
#得物笔试#
全部评论
大佬,有没有第二题题解也出一个
点赞 回复 分享
发布于 09-24 23:40 江苏
太强了佬
点赞 回复 分享
发布于 09-25 14:21 北京

相关推荐

09-24 21:05
中南大学 C++
点赞 评论 收藏
分享
4 3 评论
分享
牛客网
牛客企业服务