這篇文章來介紹一下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處理不了帶有負權環的圖），當然要是題目告訴了不存在負權環就不需要了）。
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<l[e]){
l[e]=l[x]+b[j].z;
p[e]=x;
if(dd[e]==false)dd[e]=true,d[++t]=e;//dd數組記錄的是當前點是否在隊列中，如果不在就將其入隊；
//dd判斷的是該點是否在隊中（所以可以用bool類型）
}
if(b[j].next==0)break;//如果鄰接表中在此之前沒有以當前點為起點的邊那麼就打斷循環
j=b[j].next;
}
dd[x]=false;//對當前點所連的所有點已經進行了松弛操作，那麼這個點就會出隊，那麼它的狀態便是不在隊中了
//如果題目中可能存在負環，那麼需要開一個數組記錄這個點的入隊次數，超過n次則證明存在負環
x=d[++h];//將x換為隊首元素
}
//執行完以上代碼後，l[i]則代表的是起點到當前點的最短距離
