初赛和复赛：

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

决赛：

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

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

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

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