✨ 全新设计的 Daydream 主题，强大的功能集成为你提供优雅的体验。欢迎使用。

Codeforces Round #371 Div1 ABC 题解

我回来啦！！希望尽早康复 QwQ

好像是第一次打 div1？

SPFA 算法总结

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

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

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

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

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

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