前向星+SPFA（很强大，非常强大）

前向星+SPFA算法详解 本文将详细介绍前向星+SPFA算法的原理、实现和应用，包括SPFA算法的基本概念、前向星的实现细节和SPFA算法在实际问题中的应用。 SPFA算法 SPFA（Shortest Path Faster Algorithm）是一种计算单源最短路径的算法，能够在O(kE)时间复杂度内求出源点到其他所有点的最短路径。该算法可以处理负边，且在实现上比Dijkstra或Bellman-Ford算法更简单。 SPFA算法的基本思想是维护一个队列，队列中存放所有需要进行迭代的点。初始时队列中只有一个点S。用一个布尔数组记录每个点是否处在队列中。每次迭代，取出队头的点v，依次枚举从v出发的边v->u，设边的长度为len，判断Dist[v]+len是否小于Dist[u]，若小于则改进Dist[u]，将Fa[u]记为v，并且由于S到u的最短距离变小了，有可能u可以改进其他的点，所以若u不在队列中，就将它放入队尾。 前向星 前向星是一种邻接表的紧缩存储形式。它将边按照前端点排序，并用一个数组k[i]记录端点i第一次以左端点出现的位置。这样，我们就能用O(E)的空间复杂度存储下一个邻接表，而避免了链表或N^2的庞大空间消耗。 在实际实现中，我们并不需要排序，因为我们只需要知道某一条边应该放到什么位置即可。因此，我们还需要一个数组t[i]存储从i出发的边的条数。则需要存储在的位置就可以很轻易地求得。 Butter题目代码 以下是Butter题目的代码实现： ```pascal Program butter(input,output); Type edge=record x,y,d:longint; end; Var min,res,n,p,c,x,y,i,j,l,r:longint; te,e:array[0..3000] of edge; tk,t,k,num,d:array[1..800] of longint; q:array[1..100000] of longint; use:array[1..800] of boolean; ... ``` 该代码实现了使用前向星+SPFA算法来求解Butter题目。 前向星+SPFA算法是一种高效的计算单源最短路径的算法，能够在实际问题中发挥重要作用。