这篇文章来介绍一下spfa（Shortest Path Faster Algorithm）这种算法

这是一种单源最短路的一种十分高效的的算法。

我们需要用邻接表来存储一下图，以及用队列进行优化。

我们以1为起点，以n为终点来讲一下（一共n个点）

用L数组记录当前点的最短路

先把每一条边的最短路赋成最大值（赋多少自己决定，反正得大一点）

我们先把1入队

因为我们用的是队列进行优化，所以每次取出队首元素s，对s所连接每一个点x进行如下操作

如果L[s]+s--x的长度比L[x]要短，那么便更新L[x]，再判断x是否已经入队，若没有入队，则将x放入队中（这里需要注意一点，若x这个点入队的次数已经超过了n次，那么说明有负权环（spfa处理不了带有负权环的图），当然要是题目告诉了不存在负权环就不需要了）。

注：spfa求最短路不能有负权环可以有正权环，求最长路不能有正权环可以有负权环。   判断同上。

 

void add(int aa,int bb,int cc){ b[++cnt].v=bb;//当前点所连的边 b[cnt].next=hh[aa];//上一条以当前点为起点的边的序号 b[cnt].z=cc;//路的长度 hh[aa]=cnt;//邻接表中最近的一条起点为当前点的边的序号    }int main(){ scanf("%d %d",&n,&m); for(i=1;i<=m;i++) {  scanf("%d %d %d",&x,&y,&w);//起点，终点，长度  add(x,y,w);add(y,x,w);//邻接表用来存边，当然，如果是单向边的话，                                                                       // 就只做其中一个 }  memset(l,0x3f,sizeof(l));//将每一条路的最短距离赋为最大值 l[1]=0;//起始点为点1，所以到点1的最短距离是0 x=1;//现在的x为起点，当然也可以是其它点 while(1) {  if(h>t)break;  j=hh[x];  while(1)  {   e=b[j].v;   if(l[x]+b[j].z