发表于 | 分类于 ，
字数统计: 895 | 阅读时长 ≈ 5
SPFA是按照 FIFO 的原则更新距离的, 没有考虑到距离标号的作用。实现中 SPFA 有两个非常著名的优化: SLF 和 LLL。 SLF：Small Label First 策略，设要加入的节点是j，队首元素为i，若dist(j) < dist(i)，则将j插入队首，否则插入队尾。 1 ...
阅读全文 »

发表于 | 分类于 ，
字数统计: 392 | 阅读时长 ≈ 2
偶然间从一篇博客上看到了make_pair，所以顺便记录下来。博客地址：pair与make_pair std::pair主要的作用是将两个数据组合成一个数据，两个数据可以是同一类型或者不同类型。例如std::pair<int,float> 或者 std::pair<double,d ...
阅读全文 »

发表于 | 分类于 ，
字数统计: 1,305 | 阅读时长 ≈ 6
单源最短路(SSSP)的算法有Dijkstra，Bellman-Ford， 两大算法优化后即为Dijkstra+heap与SPFA。 这两个优化版算法写起来非常相似。接下来就从算法思路、时间复杂度、写法和适用场景上进行对比分析。 基础算法Dijkstra时间复杂度：O(V2+E) n-1次循环 ...
阅读全文 »

发表于 | 分类于 ，
字数统计: 820 | 阅读时长 ≈ 5
问题描述一张图，共有m条路，从1走到n，一共可以使k条路的路程为0，求最短路。 思路去掉的k条路肯定全部在从1到n的某一条路径上，这样走这一条路径才有可能最短。我们可以对最短路分层，即分别求k为0，k为1，k为2……k为k的情况下最短路程。定义最短路时使用二维数组dis[n][k],n为结点数，k为 ...
阅读全文 »

发表于 | 分类于 ，
字数统计: 702 | 阅读时长 ≈ 3
在写证明过程之前，我们先回顾一下最大公约数gcd的欧几里得求法。 gcd，即最大公因数。为了书写方便，人们常习惯以gcd(a,b)表示a,b的最大公因数。那最小公倍数呢？我们知道若已知a,b,gcd(a,b),那么最小公倍数就自然等于a * b / gcd(a,b)。这里就不证明了。 我们接着看gc ...
阅读全文 »

发表于 | 分类于 ，
字数统计: 314 | 阅读时长 ≈ 2
问题描述： 求解(1 * 1! + 2 * 2! + …… + (n-2) * (n-2)! + (n-1) * (n-1)!) mod n = n - 1。 PS：n! = 1 * 2 * …… * n。 证明过程： Alice, a student of grade 66, is thinki ...
阅读全文 »

发表于 | 分类于 ，
字数统计: 923 | 阅读时长 ≈ 5
链式前向星 图的存储一般有三种：邻接矩阵、邻接表、前向星。 若图是稀疏图，边很少，开二维数组很浪费; 若点很多(如10000个点)a[10000][10000]又会爆.只能用前向星做. 前向星的效率不是很高，优化后为链式前向星，直接介绍链式前向星。 （一）链式前向星1. 结构这里用两个东西： 1 结 ...
阅读全文 »