建议使用以下浏览器,以获得最佳体验。 IE 9.0+以上版本 Chrome 31+ 谷歌浏览器 Firefox 30+ 火狐浏览器
请选择 进入手机版 | 继续访问电脑版-->
设置昵称

在此一键设置昵称,即可参与社区互动!

确定
我再想想
标签
您还可以添加5个标签
  • 没有搜索到和“关键字”相关的标签
  • 云产品
  • 解决方案
  • 技术领域
  • 通用技术
  • 平台功能
取消

孙司宇

角色:成员

话题:0

发消息
发表于2020年06月09日 18:01:28 4771
直达本楼层的链接
楼主
显示全部楼层
[参赛经验分享] 华为软件精英挑战赛冠军分享

初赛和复赛:

主要的思路就是双端搜索,先找其中一端并且存下来处理一下,相对于别的选手来说我们没有做很底层的优化,主要是迭代展开(把dfs变成for循环),以及预处理IO。

决赛:

总的来说算法应该都是相似的,优化的部分可以从两方面来说。

首先是减少cache miss: 对于边表,一些图的度数比较小的时候可以用二维数组来存边表,相对于前向星可以减少一次寻址。由于相对于原图,确定起点之后最短路图的边的数量实际上少很多,所以可以临时把最短路图存下来。记录前驱更方便维护,而且对于绝大部分点来说,前驱都只有一个,所以可以用一个数组记录第一个前驱,如果多于一个前驱,可以用其它各种数据结构,速度都是相似的,这样可以很大程度减少cache miss。

另外一些还有一些思路上的优化,比如说dijkstra的堆优化,可以发现实际上的最短路都不是特别大,而且每次新加入堆中的元素一定大于已经出堆的元素,所以可以用一个类似于筒排序的堆来维护。可以很大的提升效率。对于一些比较特殊的点,比如说出度恰好是1的点,这样的点为起点形成的最短路径一定会经过他的唯一后继,所以我们可以把他与其后继合并,这样可以减少很大一部分计算。如果以点u为起点已经计算出了达到每个点的最短路长度以及最短路图,那么u的前驱v可以继承u的结果,也就是说直接令所有最短路长度加上w(v, u),这样的话,图越稀疏,就会有越多的点的最短路不需要更新,可以减少一部分求最短路的时间,这需要先预处理scc以及简单的任务调度。


https://github.com/suniyu/HuaweiChallenge2020/


举报
分享

分享文章到朋友圈

分享文章到微博

登登登登

角色:成员

话题:1

发消息
发表于2020年06月10日 14:41:06
直达本楼层的链接
沙发
显示全部楼层

牛牛牛!暴力出奇迹,厉害!

点赞 评论 引用 举报

游客

富文本
Markdown
您需要登录后才可以回帖 登录 | 立即注册