图论——最短路——spfa

1   流程

    dist[所有点] = INF
    dist[起始点] = 0

    队列
    起始点入队并标记

    while(队列不空)
    {
        取出队头t
        st[t] = false // spfa的st代表节点是否在队列中 dij的代表是否走过
        用t更新其他所有出点(入队/标记)   
    }   

    判断是否能走

2   code

    int spfa( int u )
    {
        //memset( cnt, 0, sizeof cnt );
        memset( dist, INF, sizeof dist );
        dist[u] = 0;

        queue< int > q;
        q.push( u );
        st[u] = true;
        // for(int i=1;i<=n;i++)
        // {     
        //     st[i]=true;
        //     q.push(i);
        // }
        while( q.size() )
        {
            int t = q.front();
            q.pop();

            st[t] = false;

            for( int i = h[t]; i; i = ne[i] )
            {
                int y = e[i], z = w[i];
                if( dist[y] > dist[t] + z )
                {
                    dist[y] = dist[t] + z;
                    // cnt[y]=cnt[t]+1;
                    // if(cnt[y]>=n) 
                    //      有负环
                    if( !st[y] )
                    {
                        q.push( y );
                        st[y] = true;
                    }
                }
            }
        }

        if( dist[n] > 0x3f3f3f3f /2 )
            return -1;
        else
            return dist[n];
    }

3   spfa判断负环

    cnt[]代表到达当前点最短路的边数
    如果cnt[x] >= n ,说明至少经过n
    条边即n + 1个点, 则至少有一个点
    重复

    cnt[所有点] = 0

    初始时所有点入队

    最短距更新时cnt也更新

    判断是否 > n