续：Dijkstra更详细的信息 及SPFA

昨天晚上实在是太晚了，脑子也乱了，有些东西没想起来。现在把关于Dijkstra 的剩余部分说一下。

上一个Post里的那个实现使用邻接矩阵存储图，隐式地使用了一个只出不进的队列。由于所有边权值非负，出队顶点的ans 值随时间递增。因此该算法正确。如果使用邻接表存储，复杂度为O(V²+E)，因而还是O(V²)。但如果想要用堆或RMQ优化，则必须使用邻接表存储，不然只能是浪费。我认为这些优化在竞赛中是不必要的，性价（Programming time）比太低。

有些人说SPFA很简单，我做了一下，却不这么认为。但也必须用它，如果有负权边的话。SPFA基本是一个做了剪枝的广搜，区别是不使用广搜中的visited标志而用路径长度判断，并因而需要一个in_queue判断。实现起来大致是搜索中，每次从队首取出一个顶点，对与之邻接的顶点松弛，被松弛的入队（已经在队里的不管），没有的不管。算法中需要显式地维护一个队列，复杂程度还可接受。