Luogu P3371 单源最短路模版(SPFA版)

Luogu P3371 单源最短路模版(SPFA版)

以下是使用SPFA算法解决单源最短路的标程。为了方便我使用STL中的list存储边,如果对效率有较高要求,可以用结构体数组模拟边表,这里不再展开。

SPFA算法相比Dijkstra算法而言应用更加广泛(支持含有负权边的图),但SPFA的时间复杂度较为玄学(最坏情况下为O(N*M),在随机图下实践性很好)。

NOI系列竞赛图论题中曾多次出现卡某种算法(常是SPFA),而让另一种算法能够顺利通过的情况,建议熟练掌握SPFA、Dijkstra、Floyd三种算法,根据情况选取合适的算法。

本程序是对洛谷P3371(https://www.luogu.org/problemnew/show/3371)的解答。

  • Luogu P3371明确指定从源点出发无法到达某个点时,最短路径长度为2147483647。在实际环境下,为了避免“最小值初值不够大”的问题,常常使用 inf = (1<<30) 或 int = INT_MAX (需要声明头文件climits。若使用long long,调用最大值就是LLONG_MAX)。
  • inP数组用于存储该点是否已被加入集合,SPFA的思想类似于广度优先遍历。

备注:使用STL中的set、queue、list、stack等功能时,遍历最好使用迭代器,会大大加快程序运行速度,而且更加优雅。