得物9.24笔试,ak,第三题做法分享
代码如下,
解法就是维护最短路生成树,做dijkstral的时候标记一下哪些边用过就好,唯一注意的点是当dist相同,都可以更新下一个点的最短路时,优先使用原先就有的m条边转移过来的,这部分体现到代码里就是给每条边都编号了,m条边的边的号比k条边的小,然后heap的排序优先级为距离 > 边号 > 当前点,这样每次都会让m条边的排在前面
代码是回忆版,部分地方小bug:
开始heap循环前加上一行dist【1】=0
#得物笔试#
解法就是维护最短路生成树,做dijkstral的时候标记一下哪些边用过就好,唯一注意的点是当dist相同,都可以更新下一个点的最短路时,优先使用原先就有的m条边转移过来的,这部分体现到代码里就是给每条边都编号了,m条边的边的号比k条边的小,然后heap的排序优先级为距离 > 边号 > 当前点,这样每次都会让m条边的排在前面
代码是回忆版,部分地方小bug:
开始heap循环前加上一行dist【1】=0
#得物笔试#
全部评论
大佬,有没有第二题题解也出一个
太强了佬
相关推荐