spfa算法

时间复杂度：一般为O(m), 最坏情况下则时间复杂度为O(m * n);

主要对 bellman_ford算法中的: dist[b] = min(dist[b] , dist[a] + w[a][b])进行优化

dist[b] 想要变小， 而w[a][b]不变， 所以必须dist[a]变小才能导致dist[b]变小

这一步可以使用队列进行优化.

当dist[a]变小了，并且a结点不在对列中的时候，将a存入到队列中

代码

int spfa()
{
    memset(dist,0x3f,sizeof dist);
    dist[1] = 0;
    queue<int>q;
    q.push(1);
    choose[1] = 1;
    while(q.size())
    {
        int start = q.front();
        q.pop();
        choose[start] = 0;
        for(int i = h[start]; i != -1; i = ne[i])
        {
            int j = e[i];
            if(dist[j] > dist[start] + w[i])
            {
                dist[j] = dist[start] + w[i];
                if(!choose[j]) //为什么要choose[j] == 0才把j加入进去呢?因为dist[j]已经发生了改变，如果queue中存在j点，则下次j从队列中出来的时候，自然会改变，dist[temp] = min(dist[tepm], dist[j] + w[temp][j]了。
                {
                    q.push(j);
                }
            }
        }
    }
    if(dist[n] == 0x3f3f3f3f)
    {
        return -1;
    }
    else
    {
        return dist[n];
    }
}