SPFA

复杂度$n$-$n^2

• 可以处理负权边
• 可以判负环
  贴一波代码

#include<iostream>
#include<queue>
using namespace std;
const int inf=2147483647;
queue<int > q;
int n,m,s;
struct node{
	int to;
	int next;
	int val;
}e[2000001];
int arr;
int head[1000001];
void add(int u,int v,int w){
	e[++arr].next=head[u];
	e[arr].to=v;
	e[arr].val=w;
	head[u]=arr;
}
int dis[1000001];
bool visit[1000001];
void spfa(int x){
	for(int i=1;i<=n;++i){
		if(i==x){
			dis[i]=0;
		}else{
			dis[i]=inf;
		}
	}
	q.push(x);
	visit[x]=1;
	while(!q.empty()){
		int re=q.front();
		q.pop();
		visit[re]=0;
		int k=head[re];
		while(k!=0){
			if(dis[e[k].to]>dis[re]+e[k].val){
				dis[e[k].to]=dis[re]+e[k].val;
				if(!visit[e[k].to]){
					q.push(e[k].to);
					visit[e[k].to]=1;
				}
			}
			k=e[k].next;
		}
	}
}
int main()
{
	cin>>n>>m>>s;
	for(int i=1;i<=m;++i){
		int u,v,w;
		cin>>u>>v>>w;
		add(u,v,w);
	} 
	spfa(s);
	for(int i=1;i<=n;++i){
		cout<<dis[i]<<' ';
	}
	return 0;
}

判负环
记录每一个点的搜索层数，即当前已经有超过$n$层的点，便存在负环