Bellman-Ford算法的一个问题是，每一轮都会遍历所有的边，其中很多边都是不可能被更新的，显然只有在一轮中被更新过的边才有可能使它的相邻边更新，由这个原则，我们可以用队列存入更新过的边的点，每次对它的临边进行松弛操作
时间复杂度O(km~nm)，k是每个点平均进队次数，在稀疏图中比较小，但在稠密图中会退化到Bellman-Ford算法的程度
最短路SPFA最好用BFS，而判负环DFS要快一点，BFS判负环的话可以设cnt数组储存每个点被访问的次数，入队超n次基本可以确定有负环了
例题 洛谷P3371 【模板】单源最短路径（弱化版）
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<queue>
#define forup(i,l,r) for(int i=l;i<=r;i++)
using namespace std;
vector<pair<int,int>> node[100005];
int d[100005];
queue<int> q;
bool ex[100005];//是否在队列中
int n,m,s;
void SPFA(int s)
{
d[s]=0;
q.push(s),ex[s]=true;//入队
while(!q.empty())//直到所有点都出队则说明都有最短路
{
int u=q.front();
for(auto x:node[u])
{
int v=x.first,w=x.second;
if(d[u]+w<d[v]) {//松弛操作
d[v]=d[u]+w;
if(!ex[v]) q.push(v),ex[v]=true;//只有被更新过的点所连的点才有可能更新最短路
}
}
q.pop();ex[u]=false;//出队
}
}
int main()
{
cin>>n>>m>>s;
int u,v,w;
forup(i,1,m){
cin>>u>>v>>w;
node[u].push_back({v,w});
}
memset(d,127,sizeof(d));//这个题的话这么赋值还要判一下，否则这么赋值还挺方便的。
SPFA(s);
forup(i,1,n) cout<<d[i]<<' ';
return 0;
}