SPFA算法

实质上是对bellman-ford算法的优化

//如果spfa被数据卡了可以换堆优化版dijkstra//
在Bellman-ford算法里面中的一步
dist[b]=min(dist[b],dist[a]+w);
不一定是一定要更新的。
只有dist[a]减小了才需要更新b。
可以使用队列存储变小了的节点。
做法：
首先将起点加入队列中。
while(队列不空）
    从队列中取出队头。删除队头。
    遍历取出队头的所有出边，更新。
    如果更新成功，将更新的点加入队列。（如果队列中已经存在该点则跳过加入）
   
spfa求负环：
原理类似bellman-ford，抽屉原理。
 dist[x]//表示1-x的最短距离
 cnt[x]// 1-x经过的边数
每次更新时，
    dist[x]=dist[t]+w[i];
    cnt[x]=cnt[t]+1;
当cnt>=n时，即表示有负环。

    
acwing851
acwing852//注意初始点的选择
代码待更新。