写在前面

Dijkstra的堆优化真的是不好写，首先图里面一直犯的错误又来了，访问其他点直接上邻接表的下标i，求如何提高智商？在线等，急！

以后所有的题目都无脑Dijkstra了，SPFA会被不良出题老师卡掉，Dijkstra需要记住一个东西，在堆里面的比较方式是相反的！greater是小根堆，“ < ”是大根堆比较，“ > ”是小根堆比较。被坑了，不过还好长了长记性……

Dijkstra的堆优化首先需要开一个结构体，然后定义比较方式，然后将初始点加入堆中，然后使用while循环，结束循环的条件就是当堆里面为空的时候。读堆顶，出堆，判断这个堆顶元素是否以前出过堆，如果出过就continue把，没出过就标记为出过。然后利用这个堆顶去更新和他相连的所有点，将没有出过堆的元素的加入堆中。不断的重复上面的过程直到退出。

大致过程就是这样，主要要使用邻接表，不然就是负优化的说，而且一个元素是会多次进堆的（因为大小被修改了QAQ），所以如果能直接修改堆中元素的值相比速度会提高很多，以后敲代码，如果是稠密图并且时间够，就直接上Dijkstra+堆优化，如果是稀疏图，时间不是太多，直接SPFA，其实SPFA性价比最高，但是担心被卡，还有稠密图表现也不是太好……总之努力提高代码能力，以后据情况来选择算法QAQ

NOIP级别的比赛直接上SPFA吧，想必出题老师也不会卡数据的……

堆优化代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
void Dijkstra(int Point)//经过堆优化
{
    struct note
    {
        int ID;
        int Value;
        friend bool operator < (note x,note y)
        { return x.Value>y.Value; }
    }f[501],This;
    struct Edge
    {
        int Point;
        int Next;
        int Value;
    }a[10000];
    priority_queue<note>Q;
    for(int i=1;i<=n;i++)
    {
        f[i].Value=123456789;
        f[i].ID=i;
    }
    f[Point].Value=0;
    Q.push(f[Point]);
    while(Q.empty()==false)
    {
        This=Q.top(); Q.pop();
        if(List[This.ID]) continue;
        List[This.ID]=true;
        for(int i=Link[This.ID];i!=0;i=a[i].Next)
        if(!List[a[i].Point]&&This.Value+a[i].Value<f[a[i].Point].Value)
        {
            f[a[i].Point].Value=This.Value+a[i].Value;
            Q.push(f[a[i].Point]);
        }
    }
}

SPFA判断负环

SPFA这种神奇的东西，可以判断负环的，首先我们只需要记录下来SPFA在运行的时候一个点进队的次数，如果这个点能够不停地更新，更新的次数如果大于n的时候，那么这里一定是存在负权回路的！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
bool SPFA(int Point)//在NOIP级别比赛就用这个了
{
    memset(dis,10,sizeof(dis));
    memset(vis,false,sizeof(vis));
    head=1;tail=1;dis[Point]=0;
    vis[Point]=true;Queue[1]=Point;
    all[Point]=1;
    while(head<=tail)
    {
        int This=Queue[head++];
        vis[This]=false;
        for(int i=Link[This];i!=0;i=a[i].next)
        {
            int That=a[i].Point;
            if(dis[This]+a[i].Value<dis[That])
            {
                dis[That]=dis[This]+a[i].Value;
                if(vis[That]==false)
                {
                    Queue[++tail]=That;
                    vis[That]=true;
                    all[That]++;
                    if(all[That]>n)
                    return false;//有负环
                }
            }
        }
    }
    return true;//没有负环
}

卡SPFA

SPFA这个算法是非常不稳定的，期望复杂度为O(K*E)，K是期望数字，E是边数（所以说稀疏图上啊！）

理论上SPFA可以被卡O(NE)级别，对比稠密图简直要GG，但是如果按照平均复杂度来说的话，大概期望的是O(2E)的吧，所以说以后低端局直接上SPFA，高端局如果图比较稠密就选择堆优化的Dijkstra……

最后

今天晚上去郑州，明天省选，希望考砸，为明年NOIP攒下坚实的RP！