spfa普通版就不写了，优化还是要的昂，spfa是可以判负环，接受负权边和重边的，判断负环只需要另开一个数组记录每个结点的入队次数，当有任意一个结点入队大于点数就表明有负环存在
1 #include<stdio.h> //spfa基本上要这些头文件
2 #include<string.h>
3 #include<queue>
4 using namespace std;
5
6 const int maxn=1e5+5;
7 const int maxm=1e5+5;
8 const int INF=0x3f3f3f3f;
9
10 int head[maxn],point[maxm<<1],nxt[maxm<<1],val[maxm<<1],size;
11 int dis[maxn],vis[maxn];
12
13 void init(){
14 memset(head,-1,sizeof(head));
15 size=0;
16 }
17
18 void add(int a,int b,int v){ //有向图只需要前一半
19 point[size]=b;
20 val[size]=v;
21 nxt[size]=head[a];
22 head[a]=size++;
23
24 point[size]=a;
25 val[size]=v;
26 nxt[size]=head[b];
27 head[b]=size++;
28 }
29
30 void spfa(int s,int t){
31 memset(vis,0,sizeof(vis));
32 memset(dis,0x3f,sizeof(dis));
33 queue<int>q;
34 vis[s]=1;
35 dis[s]=0;
36 q.push(s);
37 while(!q.empty()){
38 int u=q.front();
39 q.pop();
40 vis[u]=0;
41 for(int i=head[t];~i;i=nxt[i]){
42 int j=point[i];
43 if(dis[j]>dis[u]+val[i]){
44 dis[j]=dis[u]+val[i];
45 if(!vis[j]){
46 q.push(j);
47 vis[j]=1;
48 }
49 }
50 }
51 }
52 printf("%d
",dis[t]);
53 }