SkyWT

SkyWT

我们的征途是星辰大海

💬 博客评论 IP 错乱的问题已修复。最近更新:博客全面启用 PJAX 无刷新(221005)。
📧 现在可以使用邮箱订阅本博客。欢迎订阅!

2019.10.11 Upd:这是 ZS 时期写的一篇非常 naive 的博客,别看了。
SPFA 会被卡,Dij 才最好。


SPFA真是最好的单源最短路算法,没有之一。

SPFA全称是Shortest Path Faster Algorithm,直译过来就是“最短路更快算法”,从这个名称就能看出SPFA效率很高。SPFA加上SLF优化以后被称作单源最短路的“无敌”,时间复杂度可以达到O(ke)(k表示平均每个节点入队次数,k≤2,e表示边数),可以刷负边权。

More...


感觉今年试卷比去年简单,不过数据比去年强(似乎一群dalao因为某题一个小小的失误而350)。

NOIP2017 Junior

More...


C++ STL 里的 set,顾名思义就是集合。和数学里的集合一样,C++ STL 里的集合也具有互异性,即每个元素最多只出现一次。如果需要某个值出现多次就可以用 multiset。

集合的好处是,集合里存的元素都是从小到大排好序的。这和插排不同,集合的复杂度是 log2(n),对解决一些题目十分有用。

More...