SPFA算法是单源最短路径的最快算法，时间复杂度是O（KE）K一般为1或2，E是边数，就算他O（E）好了。

SPFA在很多教科书上都没有，主要是因为SPFA是中国人提出来的，外国人很少知道，所以就没有Dijkstra拿下算法那么热门，虽然不是很热门，但算法本身还是很好的。

SPFA是Bellman-ford的优化版，单源最短路径，可以检查出有没有负权环，最重要的是没有Dijkstra那么好卡。

SPFA主要是考虑到Bellman-ford的松弛操作有很多多余的地方，就用队列把那些多余的地方去掉了。

SPFA的算法过程是：

0、先说明一下，dist[i]表示从s到i的最短路径，map[i][j]表示从i到j这条路的权值，s表示起点，cmp[i]为i入队了多少次。

1、初始化：把dist数组设为无穷大，把dist[s]设为0，map[i][j]里，如果走得到，就放ij这条边的权值，走不到就置成INF（INF为无穷大）。

2、设一个队列q，s入队。

3、取出队列的第一个元素，用这个元素来松弛其他元素，也就是：

if(dist[v]+temp.second
     
      =n){std::cout<<-inf;return 0;}            }
     

这里用了STL的queue，和STL的pair，queue相信大家都知道，但pair知道的人就很少了，你暂且可以把它理解为一个储存两个元素的容器，XXX.first为第一个元素，XXX.second为第二个元素。

如果你想了解有关STL的pair的更多更多请访问：或

如果你想了解更过有关STL的queue请访问:或

4、如果队列为空，那么结束循环，表示SPFA算法已结束，跳到7

5、如果某个节点进队列超过n（节点数）次，就表示有负权环，输出“有负权环”，程序结束。

6、跳到3

7、输出，结束程序。

然后是上代码：

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             int dist[1001],cmp[1001];std::vector< std::list< std::pair 
             
               > > map1;std::queue
              
                q;const int inf = 0x3f3f3f3f;int main(){ int n,m,a,b,c,s; std::cin>>n>>m>>s; map1.resize(n+1); s--; for(int i = 0;i
               
                >a>>b>>c; a--;b--; std::pair
                
                  temp (b,c); map1[a].push_back(temp); } memset(dist,0x3f,sizeof(dist)); dist[s] = 0; q.push(s);cmp[s]++; while(1) { int v = q.front();q.pop(); for(std::list< std::pair
                 
                   >::iterator it = map1[v].begin();it!=map1[v].end();it++) { std::pair
                  
                    temp = *it; if(dist[v]+temp.second
                   
                    =n){ std::cout<<-inf;return 0;} } } if(q.empty()==true)break; } for(int i = 0;i