Heap+Dijkstra

练习题：http://poj.org/problem?id=3169

Dijkstra的过程

Initialization

Set dist[all]=∞ and set dist[S]=0;
push S into Heap;

Main

while (!heap.empty()) {
    HeapItem p=heap.pop();
    if (dist[p] != p.distence) // Lazy delete..
        continue; //To skip the status that in heap but not the shortest distence.
    // we could find out whether there exist a "negative loop(feedback)"
    foreach (Edge e=head[p]) {
        if (dist[e->to] > dist[p] + e->length) {//slack
            dist[e->to] = dist[p] + e->length;
            heap.push(e->to, distence=dist[e->to]);
        }
    }
}

相关知识

首先不能求负环，有负环就不存在最短路。
朴素的Dijkstra也不能求负边，由于它的贪心性质，有可能贪不到负边。
但是堆优化的Dijkstra由于某个点能重复进入while循环，因此能处理负边，但是明显可以发现复杂度有变化。
heap+dijkstra怎么排除负环：某个点i进行有效的进入while的次数>n，（即上述代码跳过lazy delete以后）显而易见啊。

SPFA是什么：是最朴素的bfs/dfs找最短路的方法，就是不断的找到一个点，扩展周边点，下一个点，再去扩展。。
相比之下dijkstra就是，把找点过程变成了贪心。
SPFA有一个叫SmallLabelFirst的优化就是：bfs时候，如果dist[新点]<dist[队列头]，插到头部，这就很像上述dijkstra了。
SPFA和这个差不多，仔细想这个要比spfa效率高，但是spfa可以处理负边。
SPFA无负环时可以求最短路，无正环可以求最长路。
附一个spfa的代码，摘自朴素的最小费用流。

int S,T;
int path[MAXN];
Edge *pathHelper[MAXN];
bool spfa(bool getMin=true)
{
    memset(path, 0xff, sizeof(path));
    int dist[MAXN];
    if (getMin) memset(dist, 127, sizeof(dist));
    else memset(dist, 128, sizeof(dist));
    auto cmp = [&](int a, int b) -> bool{ return ( getMin?(a<b):(a>b) ); };
    bool inque[MAXN]; memset(inque,0,sizeof(inque));
    list<int> Q; Q.push_back(S); dist[S]=0; inque[S]=1;

    while (!Q.empty()) {
        int x=Q.front(); Q.pop_front(); inque[x]=0;
        cout<<"spfa] "<<x<<" dist="<<dist[x]<<endl;
        for (Edge *e=head[x]; e; e=e->next)
            if (e->flow && cmp(dist[x]+e->cost, dist[e->to]) ) {
                dist[e->to] = dist[x]+e->cost;
                path[e->to]=x; pathHelper[e->to]=e;
                if (!inque[e->to]) {
                    inque[e->to]=1;
                    //optimize...
                    if (Q.size() && cmp(dist[e->to], dist[Q.front()]))
                        Q.push_front(e->to);
                    else
                        Q.push_back(e->to);
                }
            }
    }
    return path[T]!=-1;
}